Omvendt polsk notasjon

I omvendt polsk notasjon, OPN (eng: reverse polish notation, RPN) eller postfiksnotasjon, skriver man operatoren etter operandene i et matematisk uttrykk. Dette medfører blant annet at man unngår bruk av parenteser. Omvendt polsk notasjon kan betraktes som en variant av polsk notasjon, utformet av den polske matematikeren Jan Lukasiewicz som innførte notasjonen på 1920-tallet.

Eksempel: $(a+b)/(c-d)$ blir i OPN til $ab+cd-/$

Man kan skrive et uttrykk fra den ordinære infiksnotasjonen til postfiksnotasjonen ved hjelp av Dijkstras sidesporsalgoritme.

Omvent polsk notasjon ble introdusert i 1954 av Burks, Warren og Wright og ble uavhengig av dette gjennoppfunnet av F. L. Bauer og E. W. Dijkstra tidlig i 1960-årene i den hensikt å redusere behovet for datamaskinminne og for å kunne bruke stack ved behandling av matematiske uttrykk. Notasjonen og algoritmene for dette ble senere videreutviklet av den australske filosofen og vitenskapsmannen Charles Hamblin.

Behandling av regnestykker med omvendt polsk notasjon

Beregning av matematiske uttrykk skrevet med omvendt polsk notasjon er lett å utføre på en datamaskin ved hjelp av en stack. Beregningen skjer ved å lese uttrykket fra venstre mot høyre. Hver gang en operand inntreffer legges den på stacken. Når en operator inntreffer fjernes det aktuelle antall operander fra stacken, regnestykket utføres med disse operandene, og resultatet legges i stacken. Slik fortsetter beregningen til den er ferdig og det eneste som da ligger igjen i stacken er det endelige resultatet.

Omvendt polsk notasjon på regnemaskiner

Sett fra datamaskinens og regnemaskinenes «synspunkt», er omvendt polsk notasjon lettere å behandle en infiksnotasjonen, fordi regneroperatorene opptrer i den rekkefølge de skal utføres. De første matematiske bord-regnemaskiner ble markedsført og solgt før utviklingen av Integrerte kretser, og måtte derfor inneholde tusenvis av ulike elektronikkomponenter: Valget av omvendt polsk notasjon reduserte behovet for antall komponenter, og dermed også hele regnemaskinens fysiske størrelse.

I 1970-årene var teknikken bak de integrerte kretsene kommet så langt, at all elektronikk til en regnemaskin kunne samles på en av disse «chipene»: Fra nå av hadde regnemaskin-fabrikantene, fra et teknisk synspunkt, fritt valg mellom omvendt polsk notatsjon, og den mere vanlige formen – produksjonskostnaden ble uansett den samme. Enkelte fabrikanter, med Texas Instruments i spissen, valgte å benytte den mer vanlige infiksnotatsjonen, mens andre, spesielt Hewlett-Packard, fortsatt leverer lommeregnere hvor regneoppgavene skal tastes inn med omvendt polsk notatsjon.