Obrnuta poljska notacija

	Prefiksna notacija
	Infiksna notacija
	Postfiksna notacija

Postfiksna notacija ili postfiksni sustav oznaka je matematička 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 je izmislio 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 se odnosi na binarne operatore. Unarni operator za kojeg se dogovorno koristi postfiksna notacija jest faktorijela.

Objašnjenje

U postfiksnoj notaciji operatori slijede svoje operande. Na primjer, za zbrajanje tri i četiri se piše "3 4 +" mjesto "3 + 4". Ukoliko 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 je ta š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 su bazirani 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.

Praktične implikacije

Čitanjem slijeva na desno, izračuni se mogu obaviti čim je pročitan operator; obrađivanje uvijek može započeti prije nego 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 (vrjednovanje) 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.

Nedostaci

Š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 +" bi moglo izgledati kao "123 4 +").
Većina RPN elektroničkih kalkulatora imaju programibilne funkcije i višestruke memorijske registre. U formalnim ispitima su takvi kalkulatori sa proširenim funkcijama često zabranjeni, dok je korištenje jednostavnih infiksnih kalkulatora dozvoljeno.

Postfiksni algoritam

Algoritam za evaluaciju bilo kojeg postfiksnog izraza je poprilično neposredan:

Dok postoje dostupne ulazne leksičke jedinke
- Čitaj sljedeću leksičku jedinku sa ulaza.
- Ako je ta jedinka vrijednost
  - Potisni jedinku na stog.
- Inače, jedinka je funkcija. (Operatori, poput +, su jednostavno funkcije koje primaju dva formalna argumenta.)
  - Poznato je da funkcija prima n argumenata.
  - Stoga, dohvati sa vrha stoga n vrijednosti.
    - Ako postoji manje od n vrijednosti na stogu
      - (Greška) Korisnik nije unio dovoljno vrijednosti u izraz.
  - Evaluiraj funkciju, sa 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.

Primjer

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, sa 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.

Pretvorba iz infiksne notacije

Edsger Dijkstra je izmslio shunting yard algoritam ("skretničkog kolosijeka") za pretvorbu infiksnih izraza u postfiksne (RPN), i imenovao ga 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 izmjenjena tako da generiraju postfiksne izraze. Posebice, jednom kad je konstruirano apstraktno sintaksno stablo, odgovarajući postfiksni izraz je dan post-order obilaskom tog stabla.

Implementacije

Prva računala koja su implementirala arhitekture koje su omogućile RPN su bili 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 je postao svjestan Hamblinovog rada.

Tvrtka Friden je uvela RPN na tržište stolnih kalkulatora sa EC-130 modelom u lipnju 1963. Hewlett-Packard (HP) inženjeri su dizajnirali 9100A Desktop Calculator 1968. sa 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 je bio prvi džepni RPN kalkulator 1972. HP-10C serija kalkulatora, uključujući poznati financijski kalkulator HP-12C, je također 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 ih je prisilila da puste u prodaju model HP-19BII, koji je korisnicima šruž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
Unixov kalkulatorski program dc
Pisanje interpretera
Interaktivni JavaScript RPN kalkulator
JavaScript RPN kalkulator sa tipovničkim korisničkim sučeljem, poput HP kalkulatora
RPN kalkulator napisan u Javi otvorenog koda za mobitele
Linux IpTables "Rope" programski jezik
Sinclair kalkulatori

Vidi još

Prefiksna notacija (poljska notacija)

Vanjske poveznice

Online HP-35 RPN Calculator– 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 – 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