Omvänd polsk notation
Omvänd polsk notation (RPN, eng. Reverse Polish notation) är en metod, som gör det möjligt att skriva aritmetiska uttryck utan att använda parenteser.
Notationen, som skapades av den polske logikern Jan Łukasiewicz, kallas även för postfixnotation eftersom operatorn skrivs efter operanderna. Polsk notation är på motsvarande sätt en prefixnotation, där operatorn skrivs före operanderna. Av dessa två beteckningssätt är omvänd polsk notation det mest använda. Metoden används vid beräkningar med miniräknare och datorer, där en stack finns implementerad.
Historik
Notationen infördes omkring 1920 av den polske matematikern Jan Łukasiewicz. Omvänd polsk notation aktualiserades 1968 då Hewlett-Packard introducerade sin första programmerbara tekniska kalkylator HP 9100A. Denna var stack-baserad och saknade tangenter för parenteser. För inmatning av en operand i stacken, används en särskild inmatningstangent, så kallad uppåtpil. Anledningen till att HP valde omvänd polsk notation var att kalkylatorn skulle kunna evaluera godtyckliga uttryck, men den då tillgängliga teknologin tillät inte att man beräknade sådana uttryck med parenteser. En bieffekt av denna konstruktion var att antalet nödvändiga tangenttryckningar kunde minimeras, vilket också var värdefullt i en programmerbar kalkylator med begränsat minnesutrymme. Den klassiska Enter-tangenten, som blivit en symbol för omvänd polsk notation på kalkylatorer, introducerades 1972 på miniräknaren HP 35.
Omvänd polsk notation är lätt att hantera för en dator och förekommer i all tolkning av aritmetiska uttryck i programspråk. Denna notation är ett mellansteg när programspråkets notation översätts till datorns maskinkod. En del programspråk, som Forth och PostScript, använder denna notation direkt. Detsamma gäller de flesta flyttalsprocessorer.
Exempel
Betrakta följande uttryck:
Med en miniräknare baserad på vanlig så kallad infixnotation, skulle en beräkning kräva fjorton knapptryckningar:
- a × ( b + c ) ÷ ( d + e ) =
Med en miniräknare baserad på omvänd polsk notation krävs endast elva stycken. Man påbörjar inmatningen av symbolerna inifrån parenteser och går utåt:
b [ENTER] c + Man lägger till b på stacken och adderar c, a × multiplicerar resultatet med a, d [ENTER] e + lägger till d på stacken och adderar e och ÷ avslutar med att dividera det förra resultatet med det senaste.
Operatorn verkar alltså på de närmast föregående operanderna, och beräkningens mellanresultat blir inplacerade där de tidigare argumenten och operatorn finns i uttrycket. Exempelvis kan det tidigare uttrycket i stället beräknas i följande steg:
abc + × de + ÷ (x ← b + c) ax × de + ÷ (y ← a × x) yde + ÷ (z ← d + e) yz ÷ (w ← y ÷ z) w (slutresultatet)
Källor
- Donald Ervin Knuth, The Art of Computer Programming, Volume 1, Fundamental Algorithms, Addison-Wesley Publishing Company, Menlo Park, California, 1973.