nav_dugme codeBlog codeBlog
  • početna Početna stranica
  • Sačuvani članci Sačuvani članci
  • Učionica
  • Saveti
  • Zanimljivosti
  • Kontakt

Postfiksna notacija - kako računari računaju?

Viber
zoom_plus zoom_minus bookmark

Uvod

Uobičajeni način zapisivanja izraza u matematici 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 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 - pa se do vrednosti izraza dolazi na nedvosmislen način (na primer, u izrazu: 5 * (2 + 4), prvo se 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.

Verovatno ne deluje intuitivno na prvi pogled, ali, računari izraze nalik na ab+ i ab+cd-/, zapisane u tzv. postfiksnoj notaciji, rešavaju mnogo brže od izraza u infiksnoj notaciji (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 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 nedostatak sposobnosti računara da odjednom sagleda "š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), a to naravno nepovoljno utiče na brzinu izvršavanja programa.

Možemo reći i ovako: sasvim je moguće napisati program koji će osposobiti računar da "sagleda širu sliku", ali je takav algoritam znatno manje efikasan od postupka koji je tema članka.

Mogao bi se (zarad diskusije) izneti i argument 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, međutim:

  • kao programeri, u obavezi smo da uvek tražimo lepa i efikasna 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 je posebno 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 računaju matematičke izraze, kako se onda mogu koristiti za komplikovanije zadatke?!"), ali problem je rešio holandski naučnik Edsger 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.

Ukoliko želite da "stvari postavite u perspektivu", zamislite da je pokretanje osnovnih programa za izračunavanje izraza na prvobitnim računarima (figurativno) nalikovalo pokušaju da se na mobilnom telefonu sa početka 21. veka pokrene program za tabelarne proračune.

U stvarnosti, situacija je manje drastična (a sa druge strane - možda i još više drastična; teško je zapravo proceniti iz sadašnje perspektive), ali, krajem pedesetih godina XX veka, za pokretanje najosnovnijih programa bilo je potrebno više dana programiranja elektronskih sklopova, pojedinačne instrukcije su se izvršavale po nekoliko sekundi, tako da je znatno efikasniji algoritam bio više nego dobrodošao!

Postfiksna notacija

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.

Prefiksna i postfiksna notacija pokazuju mnoge prednosti i u matematici, ali, ovoga puta ćemo se zadržati na primerima iz računarske industrije.

Oblik izraza u postfiksnoj notaciji

Najočiglednija odlika postfiksne notacije je (kao što smo već nagovestili) 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, 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 ćemo pokazati način na koji ljudi mogu pretvarati infiksne izraze u postfiksne, metodom sagledavanja, dok ćemo (nešto komplikovanijem) algoritamskom postupku za pretvaranje infiksnih izraza u postfiksne na računarima uskoro posvetiti nekoliko članaka.

Navedeni algoritam (Shunting Yard), za pretvaranje infiksnih izraza u postfiksne je (kao što smo već nagovestili) jedan od najvažnijih algoritama u računarskoj industriji.

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, 4 * (3 + 2) iznosi 20).

Kada u postfiksnoj notaciji zamenimo promenljive 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 pronalazimo je znak operacije sabiranja: 4 3 2 + * i pošto smo ga pronašli, uzimamo dve vrednosti sa njegove leve strane: 3 2 +.

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

Izraz postaje: 4 5 * (na sličan 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.

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 - bez dvoumljenja (za ljude), što znači da se relativno lako može osmisliti i računarski algoritam koji funkcioniše po sličnom principu - bez grananja/odlučivanja.

Iako smo naveli da ćemo o algoritmu za pretvaranje infiksnih izraza u postfiksne pisati naknadno, napomenimo odmah da je jedna od glavnih odlika ovog algoritma to da se izraz iz infiksnog zapisa može prebaciti u postfiksni (takođe) u jednom prolasku.

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 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 ranim kalkulatorima pre više decenija), ali, za sada ćemo se zadržati na postfiksnoj notaciji, 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.

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

Prebacivanje izraza iz infiksnog u postfiksni zapis

Iako u ovom članku nećemo iznositi tehničke detalje postupka kojim se izraz sa infiksnom notacijom prebacuje u postfiksni zapis (već ćemo tome posvetiti detaljne članke u budućnosti), objasnićemo ideju koja stoji iza takvog postupka, služeći se postupkom koji je svojstven ljudskom načinu razmišljanja.

U izrazu prvo treba uočiti operaciju sa najvišim prioritetom (u slučaju izraza a * (b + c) koji razmatramo, to je operacija množenja) i postaviti je u koren "stabla" izraza.

Sa leve strane će biti promenljiva a (koja u množenju učestvuje samostalno), dok će desno biti "podstablo", koje samo po sebi predstavlja operaciju sabiranja promenljivih b i c (koja se u konačnom izrazu 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 na svakom čvoru/raskršću koji predstavlja operaciju (krenuvši od korena), prvo "skreće" levo, a tek kada dođemo do krajnjeg levog čvora (u bilo kom podstablu), vraćamo se se jedan korak unazad i 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 prebacivati tek kada je celo podstablo koje je vezano za znak operacije (tj, ima koren u navedenom znaku), već prebačeno u postfiksni izraz.

Iako verujemo da nije teško zamisliti kako treba sprovesti obilazak stabla, zarad lakše orijentacije pogledaćemo šemu obilaska ponešto kompleksnijeg stabla (tamniji krugovi predstavljaju znake operacija):

obilazak stabla

Kao i obično, slika ipak vredi ~1024 reči, a prikazani princip obilaska ("držimo se leve strane - dokle god možemo; vraćamo se unazad i prelazimo desno - onda kada moramo"), naravno važi i u mnogim drugim algoritmima kojima ćemo se baviti.

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 postfiksnu notaciju - korak 1(a).

.... ali, pošto nijedan od znakova iz podstabala koja izviru iz ovog čvora nije upisan, znak množenja 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 korenog č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.

U pretposlednjem koraku, rešili smo čvor a i odmah se vratili nazad na koreni čvor, što sasvim odgovara strukturi stabla i smislu izraza, ali bismo u implementaciji prvo morali proveriti da li čvor a ima podstabla (i ako bi bilo tako, morali bismo obraditi oba podstabla čvora a pre nego što se vratimo na koreni čvor).

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.

Ispitujemo znak sabiranja ....

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

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

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 postfiksnom 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 (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 postfiksnu notaciju - 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 postfiksnu notaciju - korak 6(b) - Operator + još uvek ne smemo upisati.

Prelazimo u desno podstablo operatora sabiranja, 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.

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

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

.... i sada dati čvor možemo prebaciti u izraz sa postfiksnom notacijom, budući da je rešeno celo podstablo koje čvor nosi (to jest, oba njegova podstabla).

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 na koreni čvor ....

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 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 infiksnih izraza u izraze sa postfiksnom notacijom, a za proveru rezultata možete koristiti mini-aplikaciju ispod.

Postfiksna notacija:
--------

Za dalje istraživanje

Prefiksna notacija Postfiksna notacija Jan Lukašijevič Edsger Dajkstra
Autor članka Nikola Vukićević Za web portal www.codeblog.rs
Napomena: Tekstovi, slike, web aplikacije i svi ostali sadržaji na sajtu www.codeblog.rs (osim u slučajevima gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.codeblog.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo drugo korišćenje u komercijalne svrhe, bez eksplicitnog pismenog odobrenja autora.
© 2020-2023. Sva prava zadržana.
Viber
početna Početna > Članci > Postfiksna notacija - kako računari računaju?

Info & povezani članci Info o članku - dugme

Info

trejler_sat Datum objave: 11.11.2019.

trejler_olovka Poslednja izmena: 03.07.2022.

trejler_dokument Jezici:

trejler_teg_crveni Težina: 8/10

Shunting Yard

Implementacija - 1. deo Implementacija - 2. deo Stablo izraza (članak) Genrator stabla izraza (web aplikacija)

Povezani članci

Aritmetika velikih brojeva Binarno stablo pretrage Visinski balansirano (AVL) stablo Shunting Yard - Implementacija Strukture podataka Šta je zapravo programiranje? Dijagrami toka - osnove Zašto baš binarni brojevi? Dinamičko programiranje Optimizacija algoritama Ostali članci
In programming,the hard part isn't solving problems, but deciding what problems to solve.
Paul Graham
codeBlog codeBlog
Projekat posvećen popularizaciji kulture i veštine programiranja.
Napomena: Tekstovi i slike na sajtu www.codeblog.rs (osim u slučajevima, gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.codeblog.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo drugo korišćenje u komercijalne svrhe, bez eksplicitnog odobrenja autora.
© 2020-2023. Sva prava zadržana.
Facebook - logo
Instagram - logo
LinkedIn - logo
Twitter - logo
E-mail
Naslovna
   •
Uslovi korišćenja
   •
Obaveštenja
   •
FAQ
   •
Kontakt