Obrnuta poljska notacija
|
| Prefiksna notacija |
| Infiksna notacija |
| Postfiksna notacija |
Postfiksna notacija ili postfiksni sustav oznaka matematička je notacija u kojoj svaki operator slijedi nakon svih svojih operanada. Poznatija je kao obrnuta poljska notacija (ili samo RPN od engl. reverse Polish notation), po analogiji sa srodnom poljskom notacijom, prefiksnom notacijom koju je 1920. uveo poljski matematičar Jan Łukasiewicz.
Postfiksnu notaciju izmislio je australski filozof i računalni znanstvenik Charles Hamblin sredinom 50-ih godina dvadesetog stoljeća. Hamblin je predstavio svoj rad na konferenciji u lipnju 1957. te ga objavio 1957. i 1962.
Većina ovoga što slijedi odnosi se na binarne operatore. Unarni operator za kojeg se dogovorno koristi postfiksna notacija jest faktorijela.
U postfiksnoj notaciji operatori slijede svoje operande. Na primjer, za zbrajanje tri i četiri piše se "3 4 +" mjesto "3 + 4". Ako postoje višestruke operacije, operator je dan neposredno nakon drugog operanada, tako da bi izraz napisan u "3 - 4 + 5" u uobičajenoj infiksnoj notaciji bio zapisan kao "3 4 − 5 +" u RPN: prvo se oduzima 4 od 3, te potom na taj rezultat dodaje 5. Prednost RPN taj je što odstranjuje potrebu za zagradama koje pak zahtijeva infiksna notacija. Iako "3 − 4 + 5" može biti zapisan kao "(3 − 4) + 5", to znači nešto posve drukčije od "3 − (4 + 5)", i samo se zagrađivanjem može razriješiti nejednoznačnost među dvama značenjima. U postfiksnoj notaciji, potonje bi bilo zapisano kao "3 4 5 + −", što nejednoznačno znači "3 (4 5 +) −".
Interpreteri postfiksne notacije bazirani su na stogu. To jest, operatori su potisnuti na vrh stoga, a kad se operacija obavi, operandi su dohvaćeni sa stoga i rezultat je opet potisnut na vrh. Stogovi, a stoga i RPN, imaju tu prednost što se lako programski i sklopovski ostvaruju i stoga su vrlo brzi.
- Čitanjem slijeva na desno, izračuni se mogu obaviti čim je pročitan operator; obrađivanje uvijek može započeti prije nego što je cijeli izraz pročitan.
- Bilo koje vrste zagrada su nepotrebne.
- U RPN izračunima, nije potrebna tipka "=", kao što je potrebna u korištenju uobičajenih kalkulatora, da bi se prislilo izvršavanje izračuna i evaluacija (vrednovanje) izraza.
- S druge strane, RPN kalkulatori zahtijevaju tipku "Enter" kako bi razdvojili susjedne numeričke operande.
- Stanje je uvijek samo stog vrijednosti koje čekaju operacije. Nikad se ne može dogoditi da je operator već unesen i još čeka operande.
- Široka uporaba stanardnih uređenih jednadžbi (infiksnih) u obrazovnom sustavu (i stoga su infiksni elektronički kalkulatori norma u školskim predavaonicama) može ponekad učiniti RPN nepraktičnom, teškom i ometajućom. (S druge strane, računalu je lako pretvoriti infiksnu notaciju u postfiksnu, korištenjem poznatog Dijsktrinog shunting yard algoritma).
- Susjedni brojevi moraju biti razdvojeni bjelinama, što zahtijeva precizan rukopis kako bi se spriječila zabuna (na primjer, "12 34 +" moglo bi izgledati kao "123 4 +").
- Većina RPN elektroničkih kalkulatora imaju programibilne funkcije i višestruke memorijske registre. U formalnim ispitima takvi su kalkulatori s proširenim funkcijama često zabranjeni, dok je korištenje jednostavnih infiksnih kalkulatora dozvoljeno.
Algoritam za evaluaciju bilo kojeg postfiksnog izraza poprilično je neposredan:
- Dok postoje dostupne ulazne leksičke jedinke
- Čitaj sljedeću leksičku jedinku s ulaza.
- Ako je ta jedinka vrijednost
- Potisni jedinku na stog.
- Inače, jedinka je funkcija. (Operatori, poput +, jednostavno su funkcije koje primaju dva formalna argumenta.)
- Poznato je da funkcija prima n argumenata.
- Stoga, dohvati s vrha stoga n vrijednosti.
- Ako postoji manje od n vrijednosti na stogu
- (Greška) Korisnik nije unio dovoljno vrijednosti u izraz.
- Ako postoji manje od n vrijednosti na stogu
- Evaluiraj funkciju, s vrijednostima kao argumentima.
- Potisni vraćene rezultate, ako postoje, natrag na vrh stoga.
- Ako postoji samo jedna vrijednost na stogu
- Ta je vrijednost rezultat izračuna.
- Ako postoji više vrijednosti na stogu
- (Greška) Korisnik je unio previše vrijednosti.
Infiksni izraz "5 + ((1 + 2) * 4) − 3" može u RPN biti zapisan na sljedeći način:
- 5 1 2 + 4 * + 3 −
Izraz se evaluira slijeva na desno, s ulazima interpretiranim kako je prikazano u sljedećoj tablici (Stog je lista vrijednosti koje algoritam "stavlja sa strane" nakon što je primijenjena Operacija dana u srednjem stupcu):
| Ulaz | Operacija | Stog | Komentar |
|---|---|---|---|
| 5 | Stavi operand | 5 | |
| 1 | Stavi operand | 5, 1 | |
| 2 | Stavi operand | 5, 1, 2 | |
| + | Zbroji | 5, 3 | Uzmi dvije vrijednosti (1, 2) i stavi rezultat (3) |
| 4 | Stavi operand | 5, 3, 4 | |
| * | Množi | 5, 12 | Uzmi dvije vrijednosti (3, 4) i stavi rezultat (12) |
| + | Zbroji | 17 | Uzmi dvije vrijednosti (5, 12) i stavi rezultat (17) |
| 3 | Stavi operand | 17, 3 | |
| − | Oduzmi | 14 | Uzmi dvije vrijednosti (17, 3) i stavi rezultat (14) |
Jednom kad je računanje gotovo, konačni rezultat ostaje jedina vrijednost na vrhu stoga - u ovom slučaju, to je 14.
Edsger Dijkstra izmislio je shunting yard algoritam (algoritam "skretničkog kolosijeka") za pretvorbu infiksnih izraza u postfiksne (RPN) te ga imenovao tako pošto njegovo djelovanje sliči onom od željezničke skretnice.
Postoje i drugi načini pretvorbe infiksnih izraza u postfiksne. Većina parsera tehnikom prednosti operatora može biti izmijenjena tako da generiraju postfiksne izraze. Posebice, jednom kad je konstruirano apstraktno sintaksno stablo, odgovarajući postfiksni izraz jest dan post-order obilaskom tog stabla.
Prva računala koja su implementirala arhitekture koje su omogućile RPN bili su KDF9 strojevi tvrtke English Electric, koji su bili najavljeni 1960. i postali komercijalno dostupni od 1963. godine, te američki Burroughs B5000, najavljeni 1961. i također dostupni od 1963. Jedan od dizajnera B5000 modela, R. S. Barton, kasnije je pisao kako je razvio RPN nezavisno od Hamblina negdje oko 1958. dok je čitao udžbenik o simboličkoj logici, i prije nego što je postao svjestan Hamblinovog rada.
Tvrtka Friden uvela je RPN na tržište stolnih kalkulatora s EC-130 modelom u lipnju 1963. Hewlett-Packard (HP) inženjeri dizajnirali su 9100A Desktop Calculator 1968. s RPN. Ovaj je kalkulator popularizirao RPN u znanstvenim i inženjerskim krugovima, iako prve reklame za 9100A uopće nisu spominjale RPN. HP-35 model znanstvenog kalkulatora bio je prvi džepni RPN kalkulator 1972. HP-10C serija kalkulatora, uključujući poznati financijski kalkulator HP-12C, također je koristila RPN. Kad je HP uveo kasniji model poslovnog kalkulatora HP-19B bez podrške za RPN, povratna sprega od strane financijera i drugih korisnika koji su navikli koristiti model 12-C prisilila ih je da puste u prodaju model HP-19BII, koji je korisnicima pružio mogućnost odabira algebarske notacije ili RPN.
Postojeće implementacije koje koriste postfiksnu notaciju uključuju:
- Mac OS X Calculator
- Programski jezik Forth
- Programski jezik Factor
- Hewlett-Packard znanstveni/inženjerski kalkulatori
- PostScript jezik za opis izgleda stranice
- TI-68k (TI-89) implementacija Arhivirana inačica izvorne stranice od 26. ožujka 2007. (Wayback Machine)
- Unixov kalkulatorski program dc
- Pisanje interpretera
- Interaktivni JavaScript RPN kalkulator
- JavaScript RPN kalkulator s tipovničkim korisničkim sučeljem Arhivirana inačica izvorne stranice od 5. prosinca 2006. (Wayback Machine), poput HP kalkulatora
- RPN kalkulator napisan u Javi otvorenog koda za mobitele
- Linux IpTables "Rope" programski jezik Arhivirana inačica izvorne stranice od 17. travnja 2007. (Wayback Machine)
- Sinclair kalkulatori Arhivirana inačica izvorne stranice od 3. rujna 2013. (Wayback Machine)
- Prefiksna notacija (poljska notacija)
- Online HP-35 RPN Calculator Arhivirana inačica izvorne stranice od 13. prosinca 2006. (Wayback Machine)– Prvi RPN kalkulator tvrtke Hewlett Packard
- RPN ili DAL? Kratka analiza obrnute poljske notacije protiv DAL (Direct Algebraic Logic), autora Jamesa Redina
- Mini-predavanje o postfiksnoj notacija – autora Boba Browna
- Internetski RPN kalkulator Arhivirana inačica izvorne stranice od 29. lipnja 2006. (Wayback Machine) – autora Tima Stalla
- XCALC: Besplatni RPN kalkulator za Windowse – autora Bernta Ribbuma
- GRPN: Grafički RPN kalkulator za Unix sustave (GPL) – autora Paula Wilkinsa
- Calcium: besplatni RPN kalkulator za S60 smartphone uređaje – autora mtvoid
- YaRPNcalc: Besplatni RPN kalkulator za PocketPC – autora Philippa Tschannena