Poola pöördkuju

Poola pöördkuju ehk postfikskuju on matemaatiline üleskirjutussüsteem, kus operaatorid kirjutatakse operandide järele. Näiteks infikskujul tehe 1 + 2 oleks Poola pöördkujus 1 2 +. Lisaks mainitutele kasutatakse ka Poola kuju ehk prefikskuju. Kui iga operaatori aarsus on teada, ei vaja prefikskuju ega Poola pöördkuju sulgusid, seega avaldise esitus on lühem kui infikskujul.

Poola kuju leiutas poolakas Jan Łukasiewicz
 1924. aastal. Soovides vähendada arvuti mälukasutust ning teha rohkem arvutusi pinupõhiselt pakkusid Arthur Burks, Don Warren ja Jesse Wright 1954. aastal avaldiste väärtustamiseks välja Poola pöördkuju. Eelnevast sõltumatult tulid 1960. aastate alguses samale ideele ka Friedrich L. Bauer ja Edsger W. Dijkstra.

Poola pöördkuju sai tuntumaks, kui 1970. ja 1980. aastatel kasutas Hewlett-Packard seda paljudes oma taskukalkulaatorites. Arvutiteaduses kasutatakse Poola pöördkuju pinukeele arvutusmudelit kasutavates programmeerimiskeeltes, mille tuntuim näide on Forth.

Avaldiste Poola pöördkujus esitamine

Poola pöördkujus järgnevad operaatorid operandidele. Näiteks tehte  väärtus on 5. Kui avaldis on pikem, on oluline täpsustada, et operaator järgneb vahetult viimasele operandile. Näiteks tehe  on ilmutatult korrutis , saades tulemuseks arvu 1 ning arvude 2 ja 3 summa korrutise.

Selle kokkuleppe, et operaator järgneb vahetult viimasele operandile, tõttu polegi vaja Poola pöördkujus kasutada sulge. Sulgude vältimiseks on veel oluline, et teaksime alati, mitu operandi iga operaator võtab. Seetõttu ei saa näiteks unaarse ja binaarse miinuse jaoks sama operaatorit kasutada. Võimalik on kasutada eraldi operaatorit või kui avaldissümbolite piirid on eristatud, saab kasutada märgiga täisarve. Viimane variant teeb unaarse miinuse ebavajalikuks.

Poola pöördkuju  on samaväärne infikse avaldisega . Avaldise  ehk lihtsalt  esitamiseks tuleb Poola pöördkujus kirjutada .

Väärtustamine

Enamasti kasutatakse Poola pöördkujus avaldiste väärtustamiseks pinu ning loetakse avaldist vasakult paremale. Pinu on andmestruktuur, kuhu saab peale elemendi lisada ning kust pealmise (viimati lisatud) elemendi võtta.

Kui avaldises vasakult paremale liikudes tuleb vastu mõni operand, siis lihtsalt lisatakse ta pinusse. Kui avaldise väärtustamisel jõutakse operaatorini, võetakse pinust operaatorile vastav hulk operande, teostatakse tehe ning lisatakse tulemus uuesti pinusse.

Operaatorile vastava arvu operandide võtmine tähendab tavaliste binaarsete operatsioonide (liitmine , lahutamine  jt) puhul pinust kahe elemendi võtmist, kuid näiteks unaarse operatsiooni faktoriaal  puhul võetakse pinust vaid pealmine element.

Kui operaatori kirjeldatud tehe pole sümmeetriline, siis on oluline ka see, mis järjekorras saavad pinust võetud elemendid operaatori argumentideks. Poola pöördkuju väärtustamise puhul saab pinu pealmine argument operaatori viimaseks argumendiks, järgmine eelviimaseks jne.

Näide

Olgu näiteks  Poola pöördkuju avaldis, mida soovime väärtustada. See avaldis on samaväärne infikse avaldisega . Järgnevas tabelis on kujutatud, kuidas saame seda Poola pöördkujus avaldist pinu kasutades ning avaldissümbolhaaval läbides väärtustada.

 Sümbol  Liik  Pinu  Tegevus 15  Operand  15  Lisa pinusse. 7  Operand  15 7  Lisa pinusse. 1  Operand  15 7 1  Lisa pinusse. 1  Operand  15 7 1 1  Lisa pinusse. +  Operaator  15 7 2  Võta pinust 2 elementi (1, 1), arvuta () ja lisa tulemus pinusse. −  Operaator  15 5  Võta pinust 2 elementi (7, 2), arvuta () ja lisa tulemus pinusse. ÷  Operaator  3  Võta pinust 2 elementi (15, 5), arvuta () ja lisa tulemus pinusse. -3  Operand  3 -3  Lisa pinusse. ×  Operaator  -9  Võta pinust 2 elementi (3, -3), arvuta () ja lisa tulemus pinusse. 2  Operand  -9 2  Lisa pinusse. 1  Operand  -9 2 1  Lisa pinusse. 3  Operand  -9 2 1 3  Lisa pinusse. !  Operaator  -9 2 1 6  Võta pinust 1 element 3, arvuta () ja lisa tulemus pinusse. +  Operaator  -9 2 7  Võta pinust 2 elementi (1, 6), arvuta () ja lisa tulemus pinusse. +  Operaator  -9 9  Võta pinust 2 elementi (2, 7), arvuta () ja lisa tulemus pinusse. −  Operaator  -18  Võta pinust 2 elementi (-9, 9), arvuta () ja lisa tulemus pinusse.

Viited

Kategooria:Matemaatika