Omvendt polsk notation

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

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-/

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

Behandling af regneudtryk på omvendt polsk notation[redigér | redigér wikikode]

Beregning af udtryk skrevet med omvendt polsk notation 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.

Omvendt polsk notation på regnemaskiner[redigér | redigér wikikode]

Set fra computeres og regnemaskiners "synspunkt", er omvendt polsk notation nemmere at behandle end infixnotationen, fordi regneoperatorerne optræder i den rækkefølge de skal udføres. De første matematiske "bord-regnemaskiner" blev markedsført før det integrerede kredsløb, og måtte derfor samles af tusindvis af diskrete elektronikkomponenter: Valget af omvendt polsk notation mindskede det nødvendige antal komponenter, og dermed også hele regnemaskinens fysiske størrelse.

I 1970'erne var teknikken bag de integrerede kredsløb nået så vidt, at al elektronikken til en regnemaskine kunne samles på én af disse "chips": Nu havde regnemaskine-fabrikanterne, set fra et teknisk synspunkt, frit valgt mellem omvendt polsk notation, og den mere gængse form – fremstillingsprisen blev alligevel den samme. Nogle fabrikanter, med Texas Instruments i spidsen, valgte at indrette deres maskiner efter den gængse infixnotation, mens andre , især Hewlett-Packard, stadig leverer lommeregnere hvor regneopgaverne skal indtastes med omvendt polsk notation.