Obrnuta poljska notacija

Izvor: Hrvatska internetska enciklopedija
Skoči na:orijentacija, traži
Postfix-dia.svg
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:

Vidi još

Vanjske poveznice

Dobavljeno iz "https://enciklopedija.cc/index.php?title=Obrnuta_poljska_notacija&oldid=44705"