Postfiksna notacija

Uvod

Uobičajeni način zapisivanja matematičkih izraza (koji podrazumeva da se znak operacije zapisuje između dva operanda), naziva se infiksna notacija i ima sledeće dobro poznate odlike: znaci operacija povezuju operande (promenljive i brojčane vrednosti), operacije množenja i deljenja imaju veći prioritet od operacija sabiranja i oduzimanja, zagrade se pojavljuju po potrebi i imaju najveći prioritet.

Shodno poznatim pravilima, do vrednosti izraza se dolazi na nedvosmislen način, kao na primer u izrazu: 5 * (2 + 4), gde se prvo obavlja sabiranje, pa tek onda množenje - i rezultat je 30.

Međutim, iako je za ljude, postupak računanja preko infiksne notacije razumljiv, jednostavan za usvajanje i (reklo bi se) prijemčiv i neproblematičan, za korišćenje u računarskoj tehnici - infiksna notacija ni iz daleka nije najbolji izbor.

Možda ne deluje intuitivno na prvi pogled, ali, izrazi nalik na ab+ i ab+cd-/, koji su zapisani u tzv. postfiksnoj notaciji, na računarima se rešavaju mnogo brže od infiksnih izraza kao što su a+b i (a+b)/(c-d).

U nastavku ćemo se pozabaviti time kako se infiksni izrazi pretvaraju u postfiksne, kao i time kako se računa vrednost postfiksnog izraza, a za sam početak, prodiskutovaćemo detaljnije o tome zašto infiksna notacija nije najoptimalniji izbor za računarske algoritme koji se tiču računanja vrednosti izraza.

Nedostaci infiksne notacije

( .... u kontekstu primene u računarskim algoritmima )

Ideja da se uobičajena infiksna notacija koristi i u računarskim algoritmima, verovatno deluje "prirodno", ali, u implementaciji takve ideje, postoje problemi koji se (najprostije rečeno), svode na to da računari nisu sposobni da odjednom sagledaju "širu sliku".

Čak ni u slučaju jednostavnog infiksnog izraza kao što je: a * (b + c), računar ne može sa sigurnošću izvršavati operacije u onom trenutku kada se pojave, već mora bar jednom proći kroz ceo izraz (u najboljem slučaju), pa se tek onda vratiti na izvršavanje operacija.

Zapravo, izraz ne mora imati čak ni dve operacije: izraz kao što je (na primer) a + b je najjednostavniji mogući - ali ni u ovom slučaju računar ne sme odmah da obavi sabiranje (sve dok ne uzme u obzir sve operande i operatore).

Moglo bi se reći da - iz današnje perspektive - ne deluje "strašno" da program (zapravo) prođe kroz izraz više puta, uzme u obzir sve operande, operatore, zagrade i .... "nekako" .... odredi prioritet izvršavanja operacija, jer u današnje vreme, čak i najslabiji procesor će sve navedeno izvršiti u malom deliću sekunde (ili, jednostavnije, ne deluje da je postupak računanja preko infiksne notacije "posebno problematičan"), međutim:

kao programeri, u obavezi smo da uvek tražimo što lepša i što efikasnija rešenja (pogotovo kada su u pitanju elementarni problemi) - i time, generacijama programera koje dolaze posle nas, ostavimo što manje 'zbrke'
poslednje što smo naveli, posebno je važilo na početku razvoja računarske industrije kada računari, ne samo da nisu bili veoma brzi, već su (naprotiv), bili prilično tromi

U praktičnom smislu, nedostatak brzine prvobitnih računara (čak i po pitanju računanja vrednosti matematičkih izraza), bio je takav da je neko vreme dovodio u pitanje početak razvoja računarske industrije ("ako računari ne mogu efikasno da rešavaju jednostavne matematičke izraze, kako se onda mogu koristiti za komplikovanije zadatke?!"), ali, problem je rešio holandski naučnik Edzger Dajkstra i ostavio pokoljenjima lep, jednostavan i efikasan postupak koji se zasniva na isto tako lepom, jednostavnom i efikasnom (ali, nimalo uobičajenom), načinu beleženja matematičkih izraza.

Postfiksna notacija (poznata još i kao Obrnuta poljska notacija), je sistem za zapisivanje matematičkih izraza, sa sledećim glavnim odlikama:

operatori se pojavljuju posle operanada
zagrade se ne pojavljuju u izrazima

Sistem zapisivanja izraza u postfiksnom obliku, razradio je australijski naučnik Čarls Hamblin sredinom pedesetih godina 20. veka, po ugledu na (idejno sličnu) prefiksnu notaciju, koju je izumeo poljski matematičar Jan Lukašijevič i objavio 1924. godine.

Na prvi pogled, zapisivanje izraza bez zagrada može delovati "čudno", ali, uz iole ozbiljnije udubljivanje, prednosti postaju veoma očigledne - pogotovo kad je u pitanju upotreba u računarskim sistemima.

Oblik izraza u postfiksnoj notaciji

Najočiglednija odlika postfiksne notacije je (kao što smo prethodno naveli), pojava znaka operacije posle operanada, pa tako na primer:

izraz a + b postaje ab+
izraz a + (b * c) postaje abc*+

Da bismo razumeli pravi smisao ovakvog načina zapisivanja (to jest, da bismo razumeli zašto postfiksni izrazi predstavljaju praktičniji način zapisa matematičkih izraza na računarima, u odnosu na infiksnu notaciju), potrebno je da sagledamo kako se računa vrednost postfiksnih izraza, kao i to kako postfiksni izrazi (uopšte) nastaju.

Postupak računanja vrednosti postfiksnog izraza pokazaćemo odmah (u nastavku), u daljem toku članka ćemo pokazati način na koji ljudi mogu pretvarati infiksne izraze u postfiksne (sagledavanjem i rasuđivanjem), dok ćemo nešto komplikovanijem algoritamskom postupku za pretvaranje infiksnih izraza u postfiksne, uskoro posvetiti nekoliko članaka.

Pri računanju vrednosti izraza, smatraćemo da promenljiva a ima vrednost 4, promenljiva b vrednost 3, a da promenljiva c ima vrednost 2, iz čega sledi da vrednost izraza a * (b + c), odnosno, izraza 4 * (3 + 2), iznosi 20.

Kada u postfiksnoj notaciji, promenljive zamenimo navedenim (konkretnim) vrednostima, izraz postaje:

4 3 2 + *.

Računanje vrednosti

Postfiksni izrazi rešavaju se na sledeći način:

posmatrajući elemente sleva nadesno, traži se prvi (ili, u opštem smislu - sledeći ), znak operacije
kada pronađemo znak operacije, nad dve vrednosti levo od znaka, obavlja se operacija koja odgovara znaku
umesto dva operanda i znaka (iz prethodnog koraka), u izrazu ostaje samo rezultat operacije
postupak se ponavlja sve dok u izrazu (posle poslednje izvršene operacije), ne ostane samo jedan operand
preostali operand predstavlja vrednost početnog izraza

U našem slučaju, prvi znak operacije koji uzimamo u obzir je znak operacije sabiranja: 4 3 2 + * i pošto smo pronašli znak +, uzimamo dve vrednosti sa njegove leve strane: 3 2 +.

Rezultat sabiranja (5), vraćamo u izraz umesto brojeva 3 i 2, a znak sabiranja uklanjamo iz izraza.

Izraz postaje: 4 5 * (na sličan način kako smo izraz 4 * (3 + 2) mogli svesti na izraz 4 * 5), pa preostaje samo da ponovimo postupak sa operacijom množenja i dobijemo rezultat 20.

Poenta je sledeća: ceo izraz se (kao što vidimo), rešava u jednom prolasku, to jest, svaka operacija se obavlja u onom trenutku kada naiđemo na znak operacije:

nema dvoumljenja (za ljude)
relativno lako se može osmisliti i računarski algoritam koji funkcioniše po sličnom principu (bez grananja/odlučivanja)

Na početku smo naveli da je najočiglednija odlika postfiksne notacije, pojava znaka operacije posle operanada, ali vidimo da je odsustvo zagrada, odnosno (praktičnije) - mogućnost izvršavanja operacija redom, bez dvoumljenja - najvažnija odlika postfiksne notacije (isto važi i za prefiksnu notaciju, na koju ćemo se ukratko osvrnuti u sledećem odeljku).

Algoritam za pretvaranje infiksnih izraza u postfiksne (koji smo u uvodnim poglavljima predstavili kao jedan od najvažnijih algoritama u računarskoj industriji), nosi naziv Shunting Yard i na ovom mestu želimo (zarad nešto starijih i iskusnijih čitalaca, koji odmah žele da se malo više udube u tematiku članka), da se osvrnemo na nekoliko važnih i zanimljivih osobina navedenog algoritma:

pretvaranje infiksnog izraza u postfiksni, obavlja se u jednom prolasku kroz izraz
računanje vrednosti (postfiksnog) izraza, takođe se obavlja u jednom prolasku kroz izraz
ideja koja se koristi za pretvaranje infiksnih izraza u postfiksne, koristi se i za prevođenje programskog koda višeg nivoa (C, C++, Java, Python i sl) - u mašinski kod

Naravno, to su samo uvodne napomene, a detaljnom opisu postupaka za pretvaranje infiksnog izraza u postfiksni i računanje vrednosti izraza, posvetićemo (u bliskoj budućnosti), više mesta u zasebnim člancima.

Ukratko o prefiksnoj notaciji

Prefiksna notacija (nije teško pretpostaviti), podrazumeva sličan pristup kao i postfiksna notacija, sa tom razlikom što se operator beleži pre operanada:

izraz a + b postaje +ab
izraz a + (b * c) postaje +a*bc

Procena vrednosti obavlja se 'u obrnutom smeru' (u odnosu na idejno sličan postupak koji smo videli u prethodnom poglavlju): u drugom izrazu, prvo se obavlja množenje, pa onda sabiranje.

"Neobrnuta" poljska notacija se takođe koristi u računarskim algoritmima (bila je posebno popularna na prvim elektronskim kalkulatorima, pre više decenija), ali, za sada ćemo se zadržati na proučavanju (i korišćenju) postfiksne notacije, budući da takav zapis (ipak) prirodnije odgovara većini algoritama.

Uglavnom, u oba slučaja, oslobodili smo se zagrada (posle čega se vrednost izraza može izračunati u jednom prolasku), pa ostaje samo još pitanje, kako da od infiksnog izraza napravimo postfiksni.

Prebacivanje izraza iz infiksnog zapisa u postfiksni

Pre upoznavanja sa 'zvaničnim' postupkom za pretvaranje infiksnih izraza u postfiksne (što ostavljamo za drugu priliku), potrebno je da se upoznamo sa idejama koje stoje iza postupka - a to ćemo najlakše izvesti ukoliko izraze predstavimo preko grafičkih simbola (ili jednostavnije, preko "slika").

U izrazu prvo treba uočiti operaciju koja, u širem kontekstu, ima najniži prioritet (to jest, operaciju koja se izvršava na kraju), i potom treba postaviti znak operacije u koren "stabla" izraza (u konkretnom izrazu koji koristimo kao primer: a * (b + c), u pitanju je operacija množenja).

Sa leve strane će biti promenljiva a (koja u množenju učestvuje samostalno), dok će, sa desne strane, biti "podstablo" koje samo po sebi predstavlja operaciju sabiranja promenljivih b i c, koja se (očigledno) obavlja pre množenja zbira b + c sa promenljivom a.

Prebacivanje infiksne notacije u postfiksnu - Stablo — Slika 1. - Prebacivanje u postfiksni zapis - početna situacija - infiksni zapis predstavljen preko stabla.

Stablo se obilazi tako što se, počevši od korena, na svakom čvoru/raskršću koji predstavlja operaciju, prvo "skreće" levo, a tek kada dođemo do 'krajnjeg levog čvora' (u bilo kom podstablu), vraćamo se se jedan korak unazad - na čvor koji predstavlja operaciju - i potom skrećemo desno. Ali - posle tog desnog skretanja (kada se nađemo u novom podstablu) - opet se prvo skreće levo (i opet se "držimo leve strane").

Kada se u kretanju kroz stablo pronađe operand (promenljiva), odmah se prebacuje u postfiksni izraz, dok operatore (znake operacija), možemo prebaciti tek kada je celo podstablo koje je vezano za znak operacije (tj, podstablo koje u korenu ima znak operacije), već prebačeno u postfiksni izraz.

Krenimo redom i pogledajmo kako postupak izgleda na primeru izraza koji smo do sada koristili: a * (b + c).

Prvo u obzir uzimamo poslednju operaciju koja se izvršava (znak množenja na vrhu stabla) ....

Prebacivanje infiksne notacije u postfiksnu - Korak 1 — Slika 2. - Prebacivanje u postfiksni zapis - korak 1(a).

.... ali, pošto nijedan od znakova iz podstabala koja izviru iz korenog čvora nije upisan, znak množenja za sada moramo preskočiti.

Prebacivanje infiksne notacije u postfiksnu - Korak 2 — Slika 3. - Prebacivanje u postfiksni zapis - korak 1(b) - operator ne možemo upisati dok nisu upisana oba njegova podstabla.

Prelazimo na levu stranu ....

Prebacivanje infiksne notacije u postfiksnu - Korak 3 — Slika 4. - Prebacivanje u postfiksni zapis - korak 2(a).

Čvor predstavlja promenljivu, pa ćemo ga odmah prebaciti u izraz sa postfiksnom notacijom.

Prebacivanje infiksne notacije u postfiksnu - Korak 4 — Slika 5. - Prebacivanje u postfiksni zapis - korak 2(b) - operand (a) možemo upisati bezuslovno.

Ponovo se vraćamo na prvi čvor ....

Prebacivanje infiksne notacije u postfiksnu - Korak 5 — Slika 6. - Prebacivanje u postfiksni zapis - korak 3(a).

.... ali, budući da ni sada nisu rešena oba podstabla korenog čvora (iako je leva strana rešena), ponovo ne možemo čvor * prebaciti u izraz sa postfiksnom notacijom.

Prebacivanje infiksne notacije u postfiksnu - Korak 6 — Slika 7. - Prebacivanje u postfiksni zapis - korak 3(b) - Operator ponovo ne možemo upisati.

Pošto u prethodnim koracima nismo završili u potpunosti sa prvim čvorom, ali jesmo završili sa njegovim levim podstablom, prelazimo na desno podstablo.

U desnom podstablu, prvo ispitujemo čvor koji odgovara operaciji sabiranja ....

Prebacivanje infiksne notacije u postfiksnu - Korak 7 — Slika 8. - Prebacivanje u postfiksni zapis - korak 4(a).

.... ali, budući da nijedno podstablo ovog čvora nije rešeno, za sada (u smislu ispisa), preskačemo operator sabiranja.

Prebacivanje infiksne notacije u postfiksnu - Korak 8 — Slika 9. - Prebacivanje u postfiksni zapis - korak 4(b) - Operator još uvek ne možemo upisati.

Prelazimo levo i pronalazimo promenljivu ....

Prebacivanje infiksne notacije u postfiksnu - Korak 9 — Slika 10. - Prebacivanje u postfiksni zapis - korak 5(a).

.... i odmah je prebacujemo u izraz sa postfiksnom notacijom.

Prebacivanje infiksne notacije u postfiksnu - Korak 10 — Slika 11. - Prebacivanje u postfiksni zapis - korak 5(b) - kao i u prethodnim situacijama, operand (b) možemo upisati odmah.

Vraćamo se (ponovo) na operator sabiranja i ispitujemo da li je spreman za prebacivanje u postfiksni izraz ....

Prebacivanje infiksne notacije u postfiksnu - Korak 11 — Slika 12. - Prebacivanje u postfiksni zapis - korak 6(a).

.... međutim, budući da desno podstablo operatora + nije rešeno, operator + i dalje ne upisujemo u postfiksni izraz.

Prebacivanje infiksne notacije u postfiksnu - Korak 12 — Slika 13. - Prebacivanje u postfiksni zapis - korak 6(b) - Operator + još uvek ne smemo upisati.

Prelazimo u desno podstablo operacije sabiranja, gde pronalazimo promenljivu .....

Prebacivanje infiksne notacije u postfiksnu - Korak 13 — Slika 14. - Prebacivanje u postfiksni zapis - korak 7(a).

.... koju odmah možemo prebaciti u izraz sa postfiksnom notacijom.

Prebacivanje infiksne notacije u postfiksnu - Korak 14 — Slika 15. - Prebacivanje u postfiksni zapis - korak 7(b) - Operand c možemo upisati odmah.

Ponovo se vraćamo na čvor + ....

Prebacivanje infiksne notacije u postfiksnu - Korak 15 — Slika 16. - Prebacivanje u postfiksni zapis - korak 8(a).

.... i sada čvor + možemo prebaciti u izraz sa postfiksnom notacijom, budući da je rešeno celo podstablo koje se odnosi na operaciju sabiranja.

Prebacivanje infiksne notacije u postfiksnu - Korak 16 — Slika 17. - Prebacivanje u postfiksni zapis - korak 8(b) - Ovoga puta možemo upisati operator (+).

Na kraju, vraćamo se na koreni čvor ....

Prebacivanje infiksne notacije u postfiksnu - Korak 17 — Slika 18. - Prebacivanje u postfiksni zapis - korak 9(a).

.... i budući da je celo stablo, osim korenog čvora, već prebačeno u izraz sa postfiksnom notacijom, možemo prebaciti i sam koreni čvor.

Prebacivanje infiksne notacije u postfiksnu - Korak 18 — Slika 19. - Prebacivanje u postfiksni zapis - korak 9(b) - Na kraju, upisaćemo i operand "*".

Cela operacija je završena: sve promenljive i svi znakovi operacija su prebačeni u postfiksnu notaciju.

Prebacivanje infiksne notacije u postfiksnu - Korak 19 — Slika 20. - Prebacivanje u postfiksni zapis - Konačni rezultat.

Ukoliko je potrebno, pogledajte ponovo ceo primer.

Prebacivanje infiksne notacije u postfiksnu - Animacija — Slika 21. - Prebacivanje u postfiksni zapis - Animacija.

Za vežbu

Na kraju, pokušajte sami da pretvorite bar nekoliko * infiksnih izraza u izraze sa postfiksnom notacijom - na papiru.

Za proveru rezultata možete koristiti mini-aplikaciju ispod (dozvoljeni znaci: mala slova, znaci operacija i zagrade).

Postfiksna notacija:
--------

Za dalje istraživanje

Prefiksna notacija Postfiksna notacija Jan Lukašijevič Edsger Dajkstra