From Wikipedia, the free encyclopedia
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.
Algoritam za evaluaciju bilo kojeg postfiksnog izraza poprilično je neposredan:
Infiksni izraz "5 + ((1 + 2) * 4) − 3" može u RPN biti zapisan na sljedeći način:
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:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.