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 [1] 1924. aastal.[2][3] Soovides vähendada arvuti mälukasutust ning teha rohkem arvutusi pinupõhiselt pakkusid Arthur Burks, Don Warren ja Jesse Wright[4] 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.[3]
Poola pöördkuju sai tuntumaks, kui 1970. ja 1980. aastatel kasutas Hewlett-Packard seda paljudes oma taskukalkulaatorites.[5][6] Arvutiteaduses kasutatakse Poola pöördkuju pinukeele arvutusmudelit kasutavates programmeerimiskeeltes, mille tuntuim näide on Forth.[7]
Avaldiste Poola pöördkujus esitamine
[muuda | muuda lähteteksti]Poola pöördkujus järgnevad operaatorid operandidele. Näiteks tehte 8 3 − väärtus on 5. Kui avaldis on pikem, on oluline täpsustada, et operaator järgneb vahetult viimasele operandile. Näiteks tehe 1 2 3 + × on ilmutatult korrutis 1 (2 3 +) ×, 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 1 2 3 + × on samaväärne infikse avaldisega 1 × (2 + 3). Avaldise (1 × 2) + 3 ehk lihtsalt 1 × 2 + 3 esitamiseks tuleb Poola pöördkujus kirjutada 1 2 × 3 +.
Väärtustamine
[muuda | muuda lähteteksti]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
[muuda | muuda lähteteksti]Olgu näiteks 15 7 1 1 + − ÷ -3 × 2 1 3 ! + + − Poola pöördkuju avaldis, mida soovime väärtustada. See avaldis on samaväärne infikse avaldisega ((15 ÷ (7 − (1 + 1))) × -3) − (2 + (1 + 3!)). 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 (1 + 1 = 2) ja lisa tulemus pinusse. |
| − | Operaator | 15 5 | Võta pinust 2 elementi (7, 2), arvuta (7 − 2 = 5) ja lisa tulemus pinusse. |
| ÷ | Operaator | 3 | Võta pinust 2 elementi (15, 5), arvuta (15 ÷ 5 = 3) ja lisa tulemus pinusse. |
| -3 | Operand | 3 -3 | Lisa pinusse. |
| × | Operaator | -9 | Võta pinust 2 elementi (3, -3), arvuta (3 × -3 = -9) 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 (3! = 6) ja lisa tulemus pinusse. |
| + | Operaator | -9 2 7 | Võta pinust 2 elementi (1, 6), arvuta (1 + 6 = 7) ja lisa tulemus pinusse. |
| + | Operaator | -9 9 | Võta pinust 2 elementi (2, 7), arvuta (2 + 7 = 9) ja lisa tulemus pinusse. |
| − | Operaator | -18 | Võta pinust 2 elementi (-9, 9), arvuta (-9 − 9 = -18) ja lisa tulemus pinusse. |
Viited
[muuda | muuda lähteteksti]- ↑ Łukasiewicz, Jan (1957). Aristotle's Syllogistic from the Standpoint of Modern Formal Logic. Oxford University Press. (Reprinted by Garland Publishing in 1987. Mall:Isbn)
- ↑ Hamblin, Charles Leonard (1962). "Translation to and from Polish notation" (PDF). Computer Journal. 5 (3): 210–213. DOI:10.1093/comjnl/5.3.210.
- ↑ 3,0 3,1 Ball, John A. (1978). Algorithms for RPN calculators (1 ed.). Cambridge, Massachusetts, USA: Wiley-Interscience, John Wiley & Sons, Inc. ISBN 0-471-03070-8.
- ↑ Burks, Arthur Walter; Warren, Don W.; Wright, Jesse B. (1954). "An Analysis of a Logical Machine Using Parenthesis-Free Notation". Mathematical Tables and Other Aids to Computation. 8 (46): 53. DOI:10.2307/2001990. JSTOR 2001990.
- ↑ Osborne, Thomas E. (2010) [1994]. "Tom Osborne's Story in His Own Words". Steve Leibson.
- ↑ Peterson, Kristina. "Wall Street's Cult Calculator Turns 30". Wall Street Journal. Originaali arhiivikoopia seisuga 16. märts 2015. Vaadatud 31. mail 2019. |archive-date=2011
- ↑ Koopman, Philip (1989). Stack computers: the new wave.