Omvendt polsk notation

Fra Wikipedia, den frie encyklopædi

I omvendt polsk notation, OPN (eng: reverse polish notation, RPN) eller postfiksnotation, som det også kaldes, skriver man operatoren efter operanderne i et udtryk. Dette medfører bl.a., at man undgår parenteser i udtryk.

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

Beregning af udtryk skrevet på OPN-form er let at udføre på en computer vha. en stak. Beregningen sker ved at læse udtrykket skrevet på OPN-form fra venstre mod højre. Hver gang en operand optræder lægges den på stakken. Når en operator optræder fjernes det relevante antal operander fra stakken, operationen udføres på disse operander og resultatet lægges på stakken. Sådan fortsættes der til beregningen er færdig og det eneste, der ligger på stakken, er det endelige resultat.

Især Hewlett-Packards lommeregnere er kendte for at anvende OPN.

Man kan skrive et udtryk om fra den gængse infixnotation til postfixnotation med Dijkstras vigesporsalgoritme.