Postfiksna notacija - (kako računari računaju?)

Nedostaci infiksne notacije algebarskih izraza

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: 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 priznati da, iako je za ljude ovakav postupak prijemčiv, za korišćenje u računarskoj tehnici, infiksna notacija 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 ovde računar ne sme da obavlja sabiranje dok ne uzme u obzir sve operande i operatore). Nije problem, reći ćete vi, proći ćemo kroz izraz više puta (uzećemo u obzir sve operande i operatore i nekako odrediti prioritet izvršavanja operacija) .... zar ne? U današnje vreme, čak i najslabiji procesor će to izvršiti u deliću sekunde. Međutim, nije uvek bilo tako (a kao programeri, i dalje smo u obavezi da vodimo računa o efikasnosti algoritama koje koristimo) ....

U stara vremena, kada su se računari tek pojavili (i bili poznati uglavnom samo ljudima iz akademskih krugova), raspolagali su procesorima veoma skromnih mogućnosti (više stotina puta sporijim od današnjih) i malim memorijskim kapacitetom (takođe višestruko manjim od današnjeg). Kao što telefon Nokia 3310 ne bi bio u stanju da pokrene programe Word, Excel ili Visual Studio, tako ni računari od pre 70+ godina nisu bili u stanju da (u iole praktičnom smislu) rešavaju izraze sa više zagrada, pa je moralo biti pronađeno bolje rešenje. Na scenu je stupila ....

Postfiksna notacija

Postfiksna 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 počnete da se grohotom smejete ovoj "nepotrebnoj" tvorevini (ili da, u najboljem slučaju, odmahnete glavom, posmatrajući je kao ponešto zanimljiv, ali i dalje poprilično nepotrebnan eksperiment), 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 + *.

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.

Prebacivanje infiksne notacije u postfiksnu - Stablo
Slika 1. - Prebacivanje u postfiksni zapis - infiksni zapis predstavljen preko stabla.

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

Prebacivanje infiksne notacije u postfiksnu - Korak 1
Slika 2. - Prebacivanje u postfiksnu notaciju - korak 1(a).

Ni jedan od znakova iz podstabala koja izviru iz ovog čvora nije upisan, pa stoga ovaj znak za sada moramo preskočiti.

Prebacivanje infiksne notacije u postfiksnu - Korak 2
Slika 3. - Prebacivanje u postfiksnu notaciju - 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 postfiksnu notaciju - 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 postfiksnu notaciju - 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 postfiksnu notaciju - korak 3(a).

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

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

Pošto u prethodnom koraku nismo završili sa prvim čvorom, moramo preći na njegovo desno podstablo. Ispistujemo znak sabiranja ....

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

.... ali, budući da njegovo podstablo nije rešeno, za sada ga preskačemo.

Prebacivanje infiksne notacije u postfiksnu - Korak 8
Slika 9. - Prebacivanje u postfiksnu notaciju - 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 postfiksnu notaciju - korak 5(a).

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

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

Vraćamo se na prethodni čvor i isputujemo da li možemo da ga upišemo ....

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

.... međutim, budući da njegovo desno podstablo nije rešeno, za sada ga preskačemo.

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

Odlazimo desno, gde pronalazimo promenljivu .....

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

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

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

Ponovni povratak na čvor sabiranja ....

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

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

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

Na kraju, vraćamo se do korenog čvora (nije valjda da ćemo i njega konačno uspeti da rešimo?!) ....

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

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

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

Cela operacija je sada 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 postfiksnu notaciju - Konačni rezultat.

Ukoliko je potrebno, pogledajte ponovo ceo primer.

Prebacivanje infiksne notacije u postfiksnu - Animacija
Slika 21. - Prebacivanje u postfiksnu notaciju - Animacija.

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.

Postfiksna notacija:
--------

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.

Postfiksna notacija:
--------

Napomena: Tekstovi i slike na sajtu www.skola-programiranja.rs (osim u slučajevima pojedinih fotografija, gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.skola-programiranja.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo korišćenje u komercijalne svrhe, bez eksplicitnog odobrenja autora i Računarskog centra SystemPro. ©SystemPro d.o.o. novembar 2019.
Autor članka Nikola Vukićević Za web portal www.skola-programiranja.rs Preuzeto sa sajta www.codeblog.rs uz odobrenje autora
Podelite sa prijateljima: