Uvod
Način zapisivanja izraza u matematici na koji ste do sada navikli (primer izraza: a + b), koji podrazumeva da znak operacije (+) stoji između dva operanda (a i b), naziva se infiksna notacija. Kao takva, ona je ljudima razumljiva i jednostavna za usvajanje: znaci operacija povezuju operande (promenljive i vrednosti), operacije množenja i deljenja imaju veći prioritet od operacija sabiranja i oduzimanja, zagrade imaju najveći prioritet, pa se do vrednosti izraza dolazi na nedvosmislen način.
Međutim, mora se primetiti da, iako je za ljude ovakav postupak (reklo bi se) prijemčiv, za korišćenje u računarskoj tehnici, infiksna notacija ni iz daleka nije najbolji izbor. Čak ni u slučaju jednostavnog izraza kao što je: a * (b + c)računar ne može sa sigurnošću izvršavati operacije u onom trenutku kada se pojave, čime se ugrožava brzina izvršavanja programa. U najboljem slučaju, računar mora bar jednom proći kroz ceo izraz, pa se tek onda vratiti na izvršavanje operacije (recimo, izraz a + b je još jednostavniji od prethodnog, ali ni u ovom slučaju računar ne sme odmah da obavlja sabiranje, sve dok ne uzme u obzir sve operande i operatore).
Naizgled ne deluje "strašno" da (zapravo) prođemo kroz izraz više puta (i uzmemo u obzir sve operande, operatore i zagrade i .... "nekako" .... odredimo prioritet izvršavanja operacija), jer u današnje vreme čak i najslabiji procesor će to izvršiti u malom deliću sekunde, međutim, kao programeri, u obavezi smo da uvek tražimo lepa i efikasna rešenja, pogotovo kada su u pitanju elementarni problemi.
Problem koji je tema ovog članka, rešio je pre šezdesetak godina holandski naučnik Edsger Dajkstra i, umesto zbrke koja bi nastala pokušajima da se vrednosti izraza na računarima računaju preko infikne notacije, ostavio pokoljenjima jedan lep, jednostavan i efikasan postupak.
Postfiksna notacija
Oblik izraza u postfiksnoj notaciji
Postfiksna notacija (poznata još i kao Obrnuta poljska notacija) je način zapisivanja matematičkih izraza u kome se znak operacije navodi posle operanada:
- izraz
a + bpostajeab+ - izraz
a + (b * c)postajeabc*+
Pre nego što odmahnete glavom posmatrajući ovu 'nepotrebnu tvorevinu' (ili, u boljem slučaju, sagledate je kao nešto donekle zanimljivo, ali naizgled nepotrebno), rarzmotrimo na koji način bi računaru ovakav zapis pomogao u rešavanju izraza.
Smatraćemo da promenljiva a ima vrednost 4, promenljiva b ima vrednost 3 i da je 2 vrednost promenljive c. Rezultat izraza a * (b + c), odnosno, 4 * (3 + 2) je 20.
Kada zamenimo promenljive konkretnim vrednostima, izraz u postfiksnoj notaciji postaje:4 3 2 + *.
Računanje vrednosti
Izraz se rešava na sledeći način:
- posmatrajući elemente sleva nadesno, tražimo prvi (sledeći) znak operacije
- kada ga pronađemo, uzimamo dve vrednosti sa njegove leve strane i obavljamo operaciju koja odgovara datom znaku
- umesto dve uzete vrednosti u izraz vraćamo rezultat izvršene operacije, a uzeti znak se uklanja iz izraza
- postupak se ponavlja dok ne dođemo do kraja, odnosno, do poslednjeg znaka operacije.
U našem slučaju, prvi znak operacije koji pronalazimo je znak operacije sabiranja: 4 3 2 + *, a potom uzimamo dve vrednosti sa njegove leve strane: 3 2 +.
Računamo rezultat ovog sabiranja, vraćamo ga u izraz umesto brojeva 3 i 2, a znak sabiranja brišemo iz izraza.
Izraz postaje: 4 5 * (na isti način kako smo izraz 4 * (3 + 2) mogli svesti na izraz 4 * 5) i preostaje samo da ponovimo postupak sa operacijom množenja i dobijemo rezultat 20.
Prebacivanje izraza iz infiksnog u postfiksni zapis
Iako ovde nećemo iznositi tehničke detalje postupka kojim se izraz sa infiksnom notacijom prebacuje u postfiksni zapis (već ćemo tome posvetiti detaljan članak u budućnosti), objasnićemo ideju koja stoji iza njega.
U izrazu koji smo do sada koristili, uočićemo operaciju koja će se izvršavati na samom kraju, posle svih ostalih oparacija. To je operacija množenja. Nju ćemo staviti u koren "stabla" koje predstavlja izraz, a sa leve strane će biti promenljiva a, dok će desno biti "podstablo" koje, samo po sebi, predstavlja operaciju sabiranja promenljivih b i c.
Stablo ćemo obilaziti tako što ćemo na svakom čvoru / raskršću (krenuvši od korena) koji predstavlja operaciju, prvo skretati levo, a tek kada dođemo do krajnjeg levog čvora, vraćati se se jedan korak unazad i skrenuti desno (ali, posle tog prvog desnog skretanja, kada se nađemo u novom podstablu, opet ćemo prvo skretati levo).
Kada se u kretanju kroz stablo pronađe operand (promenljiva), odmah se prebacuje u izraz u postfiksnoj notaciji, dok operatore (znake operacija) možemo prebacivati tek kada je celo podstablo koje je vezano za taj znak (ima koren u tom znaku), već prebačeno u postfiksni izraz.
Krenimo redom i pogledajmo kako to izgleda na primeru našeg izraza a * (b + c).
Prvo posmatramo znak množenja na vrhu stabla ....
.... ali, pošto ni jedan od znakova iz podstabala koja izviru iz ovog čvora nije upisan, ovaj znak za sada moramo preskočiti.
Prelazimo na levu stranu ....
Čvor predstavlja promenljivu, pa ćemo ga odmah prebaciti u izraz sa postfiksnom notacijom.
Ponovo se vraćamo na prvi čvor ....
.... ali, budući da ni sada nisu rešena sva podstabla ovog čvora (iako je leva strana rešena), ponovo ne možemo dati čvor prebaciti u izraz sa postfiksnom notacijom.
Pošto u prethodnom koraku nismo završili sa prvim čvorom, prelazimo na njegovo desno podstablo. Ispistujemo znak sabiranja ....
.... ali, budući da njegovo podstablo nije rešeno, za sada ga preskačemo.
Prelazimo levo i pronalazimo promenljivu ....
.... i odmah je prebacujemo u izraz sa pstfiksnom notacijom.
Vraćamo se na prethodni čvor i isputujemo da li možemo da ga upišemo ....
.... međutim, budući da njegovo desno podstablo nije rešeno, i dalje ga ne upisujemo.
Prelazimo desno, gde pronalazimo promenljivu .....
.... koju odmah možemo prebaciti u izraz sa postfiksnom notacijom.
Ponovo se vraćamo na čvor sa operacijom sabiranja ....
.... i sada smo mnogo bolje sreće: dati čvor možemo prebaciti u izraz sa postfiksnom notacijom, budući da je rešeno njegovo celo podstablo.
Na kraju, vraćamo se do korenog čvora ....
.... i budući da je celo stablo, osim korenog čvora već prebačeno u izraz sa postfiksnom notacijom, prebacujemo i sam koreni čvor.
Cela operacija je sada završena. Sve promenljive i svi znakovi operacija su prebačeni u postfiksnu notaciju.
Ukoliko je potrebno, pogledajte ponovo ceo primer.
Za vežbu
Na kraju, pokušajte sami da pretvorite bar nekoliko izraza infiksne notacije u izraze sa postfiksnom notacijom, a za proveru rezultata možete koristiti našu mini-aplikaciju.
--------
Za dalje istraživanje
Prefiksna notacija Postfiksna notacija Jan Lukašijevič Edsger Dajkstra Algoritam Shunting yard (članak na engleskom)