Juhend:Viitamismallide vead: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
Resümee puudub Märgis: Teksti peitmine |
Resümee puudub |
||
1. rida:
'''Poola pöördkuju''' ehk '''postfikskuju''' on matemaatiline üleskirjutussüsteem, kus [[operaator_(matemaatika)|operaatorid]] kirjutatakse [[operand|operandide]] järele. Näiteks [[infikskuju|infikskujul]] tehe 1 + 2 oleks Poola pöördkujus 1 2 +. Lisaks mainitutele kasutatakse ka [[Poola kuju]] ehk [[prefikskuju]]. Kui iga operaatori argumentidearv on teada, ei vaja prefikskuju ega Poola pöördkuju sulgusid, seega avaldise esitus on lühem kui infikskujul.
Poola kuju leiutas poolakas [[Jan Łukasiewicz]]
<ref name="Łukasiewicz_1957">
{{cite book |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |title=Aristotle's Syllogistic from the Standpoint of Modern Formal Logic |publisher=[[Oxford University Press]] |date=1957}} (Reprinted by Garland Publishing in 1987. {{isbn|0-8240-6924-2}})</ref> [[1924]]. aastal.<ref>{{cite journal |author-first=Charles Leonard |author-last=Hamblin |author-link=Charles Leonard Hamblin |date=1962 |title=Translation to and from Polish notation |journal=[[Computer Journal]] |volume=5 |issue=3 |pages=210–213 |url=http://comjnl.oxfordjournals.org/content/5/3/210.full.pdf |doi=10.1093/comjnl/5.3.210}}</ref><ref name="Ball_1978">{{cite book |title=Algorithms for RPN calculators |author-first=John A. |author-last=Ball |date=1978 |edition=1 |publisher=[[Wiley-Interscience]], [[John Wiley & Sons, Inc.]] |location=Cambridge, Massachusetts, USA |isbn=0-471-03070-8}}</ref>Soovides vähendada arvuti mälukasutust ning teha rohhkem arvutusi pinupõhiselt pakkusid [[Arthur Burks]], [[Don Warren]] ja [[Jesse Wright]]<ref>{{cite journal |doi=10.2307/2001990 |jstor=2001990 |title=An Analysis of a Logical Machine Using Parenthesis-Free Notation |journal=Mathematical Tables and Other Aids to Computation |volume=8 |issue=46 |pages=53 |date=1954 |author-last1=Burks |author-first1=Arthur Walter |author-link1=Arthur Walter Burks |author-last2=Warren |author-first2=Don W. |author-last3=Wright |author-first3=Jesse B.}}</ref> 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]].<ref name="Ball_1978">{{cite book |title=Algorithms for RPN calculators |author-first=John A. |author-last=Ball |date=1978 |edition=1 |publisher=[[Wiley-Interscience]], [[John Wiley & Sons, Inc.]] |location=Cambridge, Massachusetts, USA |isbn=0-471-03070-8}}</ref>
Poola pöördkuju sai tuntumaks, kui [[1970. aastad|1970.]] ja [[1980. aastad|1980.]] aastatel kasutas [[Hewlett-Packard]] seda paljudes oma taskukalkulaatorites.<ref name="Osborne_1994">{{cite web |title=Tom Osborne's Story in His Own Words |author-first=Thomas E. |author-last=Osborne |orig-year=1994 |date=2010 |publisher=Steve Leibson |url=http://www.hp9825.com/html/osborne_s_story.html }}</ref><ref name="Peterson_2011">{{cite news |url=https://www.wsj.com/articles/SB10001424052748703841904576257440326458056 |url-access=subscription |title=Wall Street's Cult Calculator Turns 30 |author-first=Kristina |author-last=Peterson |work=[[Wall Street Journal]] |access-date=31. mai 2019 |archive-url=https://web.archive.org/web/20150316030830/https://www.wsj.com/articles/SB10001424052748703841904576257440326458056}} |archivedate=4. mai 2011</ref> [[arvutiteadus|Arvutiteaduses]] kasutatakse Poola pöördkuju [[pinukeel|pinukeele]] arvutusmudelit kasutavates [[programmeerimiskeel|programmeerimiskeeltes]], mille tuntuim näide on [[Forth]].<ref>{{Raamatuviide|autor=Koopman, Philip|pealkiri=Stack computers: the new wave|aasta=1989|koht=|kirjastus=|lehekülg=}}</ref>
==Avaldiste Poola pöördkujus esitamine==
Poola pöördkujus järgnevad [[operaator_(matemaatika)|operaatorid]] [[operand|operandidele]]. Näiteks tehte {{nowrap|8 3 −}} väärtus on 5. Kui avaldis on pikem, on oluline täpsustada, et operaator järgneb vahetult viimasele operandile. Näiteks tehe {{nowrap|1 2 3 + ×}} on ilmutatult korrutis {{nowrap|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 {{nowrap|1 2 3 + ×}} on samaväärne infikse avaldisega {{nowrap|1 × (2 + 3)}}. Avaldise {{nowrap|(1 × 2) + 3}} ehk lihtsalt {{nowrap|1 × 2 + 3}} esitamiseks tuleb Poola pöördkujus kirjutada {{nowrap|1 2 × 3 +}}.
==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 [[binaarne operatsioon|binaarsete operatsioonide]] (liitmine {{nowrap|(+)}}, lahutamine {{nowrap|(−)}} jt) puhul pinust kahe elemendi võtmist, kuid näiteks [[unaarne operatsioon|unaarse operatsiooni]] [[faktoriaal]] {{nowrap|(!)}} 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 {{nowrap|15 7 1 1 + − ÷ -3 × 2 1 3 ! + + −}} Poola pöördkuju avaldis, mida soovime väärtustada. See avaldis on samaväärne infikse avaldisega {{nowrap|((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.
{| class="wikitable"
! 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 ({{nowrap|1 + 1 {{=}} 2}}) ja lisa tulemus pinusse.
|-
| − || Operaator || 15 5 || Võta pinust 2 elementi (7, 2), arvuta ({{nowrap|7 − 2 {{=}} 5}}) ja lisa tulemus pinusse.
|-
| ÷ || Operaator || 3 || Võta pinust 2 elementi (15, 5), arvuta ({{nowrap|15 ÷ 5 {{=}} 3}}) ja lisa tulemus pinusse.
|-
| -3 || Operand || 3 -3 || Lisa pinusse.
|-
| × || Operaator || -9 || Võta pinust 2 elementi (3, -3), arvuta ({{nowrap|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 ({{nowrap|3! {{=}} 6}}) ja lisa tulemus pinusse.
|-
| + || Operaator || -9 2 7 || Võta pinust 2 elementi (1, 6), arvuta ({{nowrap|1 + 6 {{=}} 7}}) ja lisa tulemus pinusse.
|-
| + || Operaator || -9 9 || Võta pinust 2 elementi (2, 7), arvuta ({{nowrap|2 + 7 {{=}} 9}}) ja lisa tulemus pinusse.
|-
| − || Operaator || -18 || Võta pinust 2 elementi (-9, 9), arvuta ({{nowrap|-9 − 9 {{=}} -18}}) ja lisa tulemus pinusse.
|}
==Viited==
| |||