Wikipedija

Obrnuta poljska 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.

Prefiksna notacija
Infiksna notacija
Postfiksna notacija

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.

Objašnjenje uredi

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.

Praktične implikacije uredi

  • Č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.

Nedostaci uredi

  • Š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.

Postfiksni algoritam uredi

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.
      • 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.

Primjer uredi

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.

Pretvorba iz infiksne notacije uredi

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.

Implementacije uredi

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:

Vidi još uredi

Vanjske poveznice uredi

Dobavljeno iz "https://hr.wikipedia.org/w/index.php?title=Obrnuta_poljska_notacija&oldid=6661663"