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, pri čemu se nameće zaključak da se mora više puta proći kroz izraz (izraz a + b je još jednostavniji, ali ni u slučaju takvog izraza računar ne sme odmah da obavlja sabiranje, sve dok ne uzme u obzir sve operande i operatore).
Zapitaćete se možda: "zašto onda jednostavno ne prođemo kroz izraz više puta?" (uzećemo u obzir sve operande i operatore i .... "nekako" .... odrediti prioritet izvršavanja operacija). U današnje vreme, čak i najslabiji procesor će to izvršiti u malom deliću sekunde.
Nećemo previše razmišljati (bolje je tako :)), o tome da li bi se ovakvo rešenje zapravo i primennjivalo tokom razvoja računarske industrije (ipak verujemo da ne bi), da holandski naučnik Edsger Dajkstra nije pre šezdesetak godina uveo u računarsku industriju jedan lep i jednostavan postupak, koji je tema ovog članka.
Pre svega, kao programeri, u obavezi smo da i sami tražimo takva, lepa i efikasna rešenja (pogotovo kada su u pitanju elementarni problemi), a, sa druge strane, iako današnji računari mogu da obave više desetina miliona operacija u jednoj sekundi, nije uvek bilo tako ....
U stara vremena, kada su se računari tek pojavili (i bili poznati uglavnom samo ljudima iz akademskih krugova), raspolagali su veoma skromnim kapacitetima (višestruko manjim od prvih mobilnih telefona), nisu bili u stanju da rešavaju izraze sa više zagrada (da ne govorimo o komplikovanijim proračunima), pa je moralo biti pronađeno bolje rešenje. Na scenu je stupila ....
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 + b, postaje: ab+.
Izraz: a + (b * c), postaje: abc*+.
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, obavljamo operaciju koja odgovara datom znaku, umesto dve uzete vrednosti stavljamo rezultat izvršene operacije, a uzeti znak brišemo iz izraza i ponavljamo postupak 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: 4 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.
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, 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 naš 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.
Drvo ć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, vratićemo se jedan korak unazad i skrenuti desno (ali, posle desnog skretanja, kada se nađemo u novom podstablu, opet ćemo prvo skretati levo).
Kada u našem kretanju kroz stablo pronađemo operand (promenljivu), odmah ćemo dati znak prebaciti u izraz postfiksne notacije, dok znake operacija možemo prebacivati tek kada je celo podstablo koje je vezano za taj znak već prebačeno u izraz postfiksne notacije.
Krenimo redom i pogledajmo kako to izgleda na primeru našeg izraza. Prvo gledamo znak množenja na vrhu stabla ....
Ni jedan od znakova iz podstabala koja izviru iz ovog čvora nije upisan, pa stoga 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, moramo preći 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, za sada ga preskačemo.
Odlazimo desno, gde pronalazimo promenljivu .....
.... koju odmah možemo prebaciti u izraz sa postfiksnom notacijom.
Ponovni povratak na čvor 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 (nije valjda da ćemo i njega konačno uspeti da rešimo?!) ....
.... 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 aplikaciju.
--------
Za dalje istraživanje
Prefiksna notacija Postfiksna notacija Jan Lukašijevič Edsger Dajkstra Algoritam Shunting yard (članak na engleskom)