Binarna stabla i algebarski izrazi (stablo izraza)
Uvod
U uvodnom članku o postfiksnoj notaciji nagovestili smo da algoritam Shunting Yard ima važnu ulogu u prevođenju programskih jezika, a u prvom članku o implementaciji algoritma Shunting Yard, naveli smo da postoji i varijanta algoritma koja omogućava kreiranje stabla izraza - umesto postfiksnog zapisa.
Stablo izraza je razgranata struktura podataka preko koje se predstavlja apstraktni oblik određenog algebarskog izraza, pri čemu je takva 'uopštena šema izraza', istovremeno: nezavisna od različitih oblika notacije o kojima smo ranije diskutovali i (na posredan način) - povezana sa sva tri.
U širem kontekstu, stabla izraza su podvrsta sintaksnih stabala opšteg tipa, preko kojih se (pri prevođenju programskog koda), struktura programa (ili delova programa, pojedinačnih naredbi, izraza i sl), predstavlja u obliku stabla. *
Sasvim je jasno da se radi o veoma zanimljivoj pojavi (kojoj ćemo u nekom trenutku posvetiti jedan ili više članaka), pri čemu će kao uvod u nešto kompleksniju strukturu sintaksnih stabala poslužiti (upravo), članak koji je pred nama, u kome ćemo se za početak baviti nešto jednostavnijim razgranatim strukturama koje su specifično namenjene predstavljanju algebarskih izraza ....
Stabla izraza - opšte ideje
Sa stablima izraza okvirno smo se upoznali još u članku o postfiksnoj notaciji):
Stablo sa slike (da se podsetimo), predstavlja infiksni izraz (a+b*c)/d, ali - isto tako - i prefiksni izraz /+a*bcd, kao i postfiksni izraz abc*+d/.
Može se primetiti i to da su operatori (tamniji čvorovi), međusobno povezani u svojevrsno "unutrašnje stablo" (i naravno, povezani sa listovima koji predstavljaju operande).
Takođe, jasno je da operand (tj. broj ili promenljiva), u stablu izraza može predstavljati samo 'list' (drugim rečima: operandi ne mogu stajati u korenu (pod)stabala).
Postorder obilazak unutrašnjeg stabla operatora određuje redosled izvršavanja operacija, odnosno: ukoliko se svaka od operacija primeni na licu mesta (onda kada dođe na red za izvršavanje), i ako se potom podstablo u čijem korenu stoji znak operacije, zameni čvorom koji predstavlja izračunatu vrednost, celo stablo može se svesti na jedan čvor - koji predstavlja vrednost izraza. *
Preko tri različite varijante DFS obilazaka (inorder, preorder i postorder), po potrebi se može rekonstruisati: infiksni, prefiksni i postfiksni zapis izraza.
Pretvaranje infiksnog izraza u stablo izraza
Stablo izraza može nastati na (bar) dva načina, ali, najčešće se radi: ili o pretvaranju infiksnog izraza u stablo izraza, ili o pretvaranju postfiksnog (ili prefiksnog izraza) u stablo izraza.
Za početak, upoznaćemo se sa postupkom koji se može shvatiti kao 'najprirodniji i najuobičajeniji' (iako ne i najlakši): za dati infiksni izraz - kreiraćemo stablo izraza.
Pretvaranje infiksnog izraza u apstraktno stablo, izvešćemo preko algoritma Shunting Yard, ali, ovoga puta, za smeštaj rezultata neće biti korišćen red za čekanje (niti bi to bilo moguće).
Umesto reda za čekanje, rezultat(i) se smešta(ju) na poseban stek.
Dakle, varijanta algoritma Shunting Yard preko koje nastaje stablo izraza, koristi - umesto pomoćnog steka i reda za čekanje (queue) - ukupno dva steka:
- stek za operatore *
- stek za stabla
Iako implementacija steka za stabla može na prvi pogled delovati i pomalo "zastrašujuće" (zbog nepoznate strukture "svih mogućih oblika stabala izraza koja se smeštaju na takav stek"), u praksi je stvar (srećom) mnogo, mnogo jednostavnija.
Struktura podataka preko koje se može referencirati celo stablo, u osnovnom (tehničkom) smislu je zapravo običan pokazivač (tj. referenca) na koren stabla:
- sam koreni čvor stabla izraza može biti bez 'potomaka' (u tom slučaju se celo stablo svodi na samo jedan operand/promenljivu/brojčanu vrednost)
- koreni čvor može imati dva potomka, koji takođe (sami po sebi) mogu biti reference na koren nekog drugog stabla (u tom slučaju, referenca na koreni čvor predstavlja pravo 'razgranato' stablo izraza)
U svakom slučaju, dovoljno je na stek smestiti samo referencu na koreni čvor bilo kog (pod)stabla, bez preterane brige o tome kako je celokupno stablo zapravo zapisano u memoriji (što svakako čini stek sa stablima znatno preglednijim).
Sledi primer ....
Primer pretvaranja infiksnog izraza u stablo izraza
Počećemo od jednostavnog infiksnog izraza ....
(a + b * c) / d
.... čije elemente prvo treba pretvoriti u tokene i smestiti u red za čekanje:
Varijanta algoritma Shunting Yard za kreiranje stabla izraza, vrlo je slična osnovnom algoritmu za kreiranje postfiksnog zapisa (sasvim očekivano), ali, u praktičnom smislu se može reći da pravila koja ćemo navesti u nastavku zapravo predstavljaju svojevrsnu kombinaciju delova algoritma za prebacivanje izraza u postfiksnu notaciju i algoritma za računanje vrednosti postfiksnog izraza (sa kojim smo se takođe upoznali):
- ako je token koji se preuzima i izbacuje iz reda - operand, potrebno je napraviti referencu na koreni čvor novog stabla (koje se sastoji samo iz korenog čvora koji predstavlja operand), i potom treba prebaciti stablo direktno na stek za stabla
- ako je token koji se preuzima i izbacuje iz reda zagrada ili znak operacije (tj. operator), token se smešta na stek za operatore (na pomoćni stek kakav smo koristili i u prethodnoj implementaciji), pri čemu se primenjuju ista pravila za smeštanje operatora na pomoćni stek kao i u prethodnoj implementaciji (na prazan stek je moguće staviti bilo koji operator, otvorena zagrada stavlja se na stek bezuslovno, zatvorena zagrada povlači pražnjenje steka, a u ostalim situacijama vodi se računa o prioritetu operatora )
- kada je vreme da se sa pomoćnog steka ukloni operator, token se ne prebacuje u stek za stabla direktno, već se sprovodi procedura za kreiranje stabla koje odgovara tokenu operacije:
- sa vrha steka za stabla skidaju se dva stabla (ona stabla koja odgovaraju operatoru)
- formira se novo stablo (od operatora i dva preuzeta stabla)
- novo stablo se postavlja na vrh steka za stabla
Pošto smo se upoznali sa pravilima, vraćamo se na primer preko koga ćemo prikazati postupak za obradu tokena.
Otvorena zagrada ....
.... smešta se na stek za operatore:
Operand a ....
.... smešta se na stek za stabla.
Operator sabiranja ....
.... smešta se na stek za operatore:
Operand b ....
.... prebacuje se (u vidu novog stabla sa jednim čvorom), na stek sa stablima:
Operator množenja ....
.... smešta se na vrh steka za operatore (shodno do sada poznatim pravilima, znamo da je dozvoljeno da se operator množenja ili deljenja postavi preko operatora sabiranja ili oduzimanja):
Operand c ....
.... prebacuje se na stek sa stablima:
Na redu je zatvorena zagrada:
U pitanju je operator čija pojava (takođe prema pravilima sa kojima smo se detaljno upoznali u člancima o algoritmu Shunting Yard), povlači pražnjenje steka sve do prve otvorene zagrade:
Prema pravilima za formiranje stabla izraza (sa kojima smo se upoznali u ovom članku), operator sa vrha steka za operatore, uparuje se sa dva stabla sa vrha steka za stabla ....
.... sva tri elementa se uklanjaju sa stekova i formira se novo stablo ....
.... i potom se novo stablo vraća na stek za stabla:
Isti postupak ponavlja se i kada na red dođe operator sabiranja:
Operator sabiranja uparuje se sa gornja dva stabla na vrhu steka za stabla ....
.... sva tri elementa se uklanjaju sa stekova, formira se novo stablo ....
.... i potom se novo stablo smešta na vrh steka za stabla:
Otvorena zagrada sa vrha steka za operatore ....
.... sada se može ukloniti:
Pošto su zagrade rešene, algoritam se vraća na red sa tokenima.
Operator deljenja (sledeći token) ....
.... smešta se direktno na prazan stek za operatore:
Preostali token, operand d ....
.... smešta se na stek sa stablima:
Budući da je red sa tokenima ispražnjen - a stek sa operatorima nije - potrebno je isprazniti stek sa operatorima (u primeru koji razmatramo, prisutan je samo operator deljenja koji je maločas ubačen).
Operator sa vrha steka za operatore, uparuje se sa dva stabla sa vrha steka za stabla ....
.... potom se sva tri elementa uklanjaju sa stekova i formira se novo stablo ....
.... i, na kraju, stablo se vraća na vrh steka sa stablima.
Budući da je sada i stek sa operatorima ispražnjen, izraz je rešen - a stablo izraza nalazi se na vrhu steka.
Pretvaranje postfiksnog izraza u stablo izraza
Za pretvaranje postfiksnog izraza u stablo izraza, postupak je (kao što smo već naveli), još jednostavniji - i pri tom se kao pomoćna struktura podataka koristi samo jedan stek.
Postupak se sastoji iz sledećih koraka:
- ako je token koji se preuzima i uklanja iz reda - operand, token se smešta direktno na stek za stabla (u daljem tekstu (samo) "stek"), u vidu stabla sa jednim čvorom
- ako je token koji se preuzima i uklanja iz reda - operator, sa steka se skidaju dva stabla i zatim se od tri navedena elementa formira novo stablo (operator je koren novog stabla, a dva stabla preuzeta sa steka predstavljaju levo i desno podstablo)
- novoformirano stablo se potom vraća na stek
- kada se isprazni red sa tokenima i kada se završe sve operacije, na vrhu steka ostaje stablo izraza
Pogledajmo primer.
Primer pretvaranja postfiksnog izraza u stablo izraza
Za primer ćemo uzeti postfiksni izraz abc*+ (koji odgovara infiksnom izrazu: a + b * c):
Operand a ....
.... smešta se na stek sa stablima:
Operand b ....
.... smešta se na stek sa stablima:
Poslednji operand, operand c ....
.... takođe se smešta na stek sa stablima:
Operator množenja (sledeći token po redu) ....
.... uparuje se sa gornja dva elementa sa steka ....
.... od tri navedena elementa formira se novo stablo ....
.... i potom se novo stablo vraća nazad na stek:
Pojava operatora sabiranja ....
.... ponovo pokreće postupak po istom obrascu: operator se uparuje sa dva stabla sa vrha steka ....
.... formira se novo stablo ....
.... i potom se stablo vraća nazad na stek:
Stablo izraza (koje predstavlja "rešenje zadatka"), nalazi se na vrhu steka.
Kao što smo naveli na početku, preko formiranog stabla izraza moguće je rekonstruisati sva tri oblika notacije (korišćenjem DFS obilazaka) i naravno - moguće je izračunati vrednost izraza.
U nastavku ćemo detaljno prikazati navedene postupke.
Kreiranje postfiksnog zapisa iz stabla izraza
Postfiksni zapis izraza kreira se postorder obilaskom stabla, pri čemu za svaki čvor važi sledeći redosled ispisivanja:
- levo podstablo
- desno podstablo
- koreni čvor
Za primer ćemo koristiti stablo koje je (na početku članka) nastalo pretvaranjem infiksnog izraza u stablo izraza:
Koreni čvor ne ispisuje se odmah, jer nisu obiđena oba podstabla korenog čvora ....
Operator sabiranja takođe se ne ispisuje, jer još uvek nije ispisan ostatak podstabla u čijem korenu stoji čvor +:
Operand a ispisuje se na licu mesta (operand ne može biti koren podstabla). *
Algoritam se vraća na operator sabiranja, i ponovo se čvor ne može ispisati, jer nije obiđeno desno podstablo:
Sledi prelazak na desno podstablo, u čijem korenu stoji operator množenja - koji se takođe ne može ispisati (ni u slučaju čvora * nije obiđen (tj. ispisan) ostatak podstabla u čijem korenu čvor * stoji):
Po prelasku na koren levog podstabla (koje odgovara operaciji množenja), nailazi se na operand b - list koji se može odmah ispisati (na slici vidimo takođe da posle operanda b nema daljeg grananja): *
Po povratku na operator množenja (koji se i dalje ne može ispisati, jer nije obiđeno desno podstablo) ....
.... algoritam prelazi na koren desnog podstabla (operacije množenja), a operand c je list, koji se može ispisati odmah (i naravno, nema daljeg grananja):
Sada se može ispisati i operator množenja (budući da su obiđena oba podstabla):
Isto važi i za operator sabiranja (obiđena su oba podstabla i čvor se može ispisati):
Međutim, po povratku na koren stabla, može se samo konstatovati da ni ovoga puta nije vreme za ispis, jer nije obrađeno desno podstablo ....
.... ali, u ovom slučaju to će biti rešeno vrlo brzo - operand d je list i može se ispisati odmah:
... i sada - pošto su obiđena oba podstabla korenog čvora - može se ispisati i sam operator / (koji stoji u korenu stabla):
Budući da je celo stablo obiđeno, zadatak je rešen:
Kreiranje prefiksnog zapisa iz stabla izraza
Prefiksni zapis izraza kreira se preorder obilaskom stabla, pri čemu za svaki čvor važi sledeći redosled ispisa:
- koreni čvor
- levo podstablo
- desno podstablo
Ponovo koristimo isto stablo kao primer, a obilazak počinje od korenog čvora, koji (shodno pravilima), može biti ispisan odmah:
Operator + takođe se može odmah ispisati, budući da je u pitanju koreni čvor podstabla:
Operand a (koji je list), takođe se može ispisati odmah:
Operator sabiranja (na koji se algoritam vraća), već je obiđen i ispisan, što znači da neće biti ponovo ispisan, ali, prelazi se na desno podstablo:
Operator množenja (kao koren podstabla), ispisuje se odmah:
Operand b (kao list), takođe se ispisuje odmah (i sledi povratak na čvor *).
Po povratku na operator množenja, može se samo konstatovati da je čvor već obiđen (tj. ispisan) ....
.... i stoga sledi prelazak na desno podstablo.
Operand c (takođe list), može se ispisati odmah:
Sledi "još jedan" povratak na operator množenja - koji se ne ispisuje (budući da je već obiđen i ispisan):
Operator sabiranja je takođe već obiđen i ispisan ....
.... a isto važi i za koreni čvor, koji je još na početku rešen (pa preostaje samo da se obradi desno podstablo).
Čvor d se može ispisati odmah:
.... a budući da nema daljeg grananja (na slici "vidimo" da je u pitanju list; u implementaciji bi operandi/listovi bili označeni na poseban način), sledi povratak na koreni čvor, ali, pošto je koreni čvor (odavno) rešen - i budući da nema čvorova koji se dalje mogu obilaziti - izraz je rešen:
Kreiranje infiksnog zapisa iz stabla izraza
Za razliku od prethodne dve procedure koje se (praktično) poklapaju sa procedurama za obilazak stabala pretrage (o kojima smo takođe detaljno pisali u 3. nastvku mini-serijala o implementaciji AVL stabla), procedura za kreiranje infiksnog zapisa je svakako složenija i podrazumeva "malo više promišljanja".
Da pojasnimo: osnovni princip obilaženja i ispisa, u idejnom smislu odgovara inorder obilasku (pri čemu za svaki čvor važe sledeća pravila):
- ispis leve strane izraza
- ispis znaka operacije
- ispis desne strane izraza
.... ali, to je samo "okvirna ideja" i bitno je razumeti da uobičajeni inorder obilazak (sa kojim smo se detaljno upoznali u prethodno pomenutom, 3. nastavku serijala o implementaciji AVL stabla) - nije postupak kojim se može kreirati infiksna notacija izraza.
U konkretnom primeru koji koristimo (vraćamo se na korektan algoritam), ispis leve strane izraza (tj. ispis levog podstabla), zahteva dodavanje zagrada, međutim - u još opštijem smislu - pri formiranju stabla, svako spajanje "leve" i "desne" strane izraza zahteva odlučivanje: da li treba (ili ne treba) levu i/ili desnu stranu izraza zapisati unutar zagrada.
Ako o svemu malo bolje razmislimo, nije teško doći do sledećeg zaključka: u trenutku kada se zapisuje znak operacije - mora već postojati formiran zapis infiksnih izraza koji odgovaraju levom i desnom podstablu i (takođe) - mora postojati informacija o prioritetu dva navedena izraza u odnosu na znak operacije preko koga se izrazi spajaju.
Na primer, ako je levi izraz: m, ako je desni izraz: n + p, i ako je izraze potrebno spojiti preko operatora množenja, jasno je da se izraz n + p mora staviti u zagradu (i rezultat je: m * (n + p)).
Algoritam
Algoritam za kreiranje inorder ispisa podrazumeva rekurzivni obilazak levog i desnog podstabla (uz pamćenje međurezultata), pri čemu za svaki čvor važe sledeći redosled izvršavanja operacija:
- rekurzivni obilazak levog podstabla uz pamćenje infiksnog zapisa i prioriteta izraza
- rekurzivni obilazak desnog podstabla uz pamćenje infiksnog zapisa i prioriteta izraza
- kreiranje inorder ispisa
Poslednji korak podrazumeva umetanje znaka operacije (koja odgovara korenu podstabla), između rezultata za levo i desno podstablo - uz prethodno dodavanje zagrada izrazima koji su nastali rešavanjem levog i/ili desnog podstabla (naravno, samo ukoliko postoji potreba za dodavanjem zagrada).
Primer
U konkretnom primeru koji razmatramo ....
.... prvo se rešava levo podstablo (crveni deo), zatim desno podstablo (plavi deo), i tek nakon obe operacije se rešeni delovi mogu spojiti preko znaka operacije (zeleni čvor).
Procedura za levo podstablo (u ponešto pojednostavljenom obliku) ....
.... podrazumeva umetanje znaka + između leve strane (čvor a) i desnog podstabla
Dakle, potrebno je upamtiti da leva strana ("a") ima prioritet 0, * i zatim se leva strana podstabla (tj. izraza), uparuje sa rezultatom rekurzivne obrade desnog podstabla:
Po "skraćenom postupku", može se zaključiti da desnom podstablu odgovara izraz b * c, čiji je prioritet 2.
Po povratku na koren levog podstabla (budući da je vreme za formiranje infiksnog izraza), prvo treba sagledati sve elemente za ispis:
- operand
a(prioritet 0) - znak
+(prioritet 1) - izraz
b * c(prioritet 2)
Operator sabiranja (koji stoji u korenu podstabla), ima niži prioritet u odnosu na operator množenja (koji stoji u korenu podstabla izraza b * c), i stoga sledi zaključak da se celo levo podstablo početnog izraza može zapisati bez zagrada:
Sada se može sagledati i početni izraz (smatraćemo da je "algoritamskim putem" obiđeno desno podstablo, pri čemu je ustanovljeno da desnom podstablu odgovara zapis "d" i prioritet 0) ....
Pre formiranja celokupnog izraza, upoznaćemo se ukratko sa pravilima za određivanje prioriteta različitih (pod)izraza u stablu.
Pri formiranju finalnog zapisa, učestvuju sledeći elementi:
- leva strana, sa izrazom
a + b * c(čiji je prioritet1) - znak operacije
/(čiji je prioritet2) - desna strana, sa izrazom
d(čiji je prioritet0)
Pošto je prioritet leve strane (u slučaju početnog izraza), praktično određen pojavom operatora sabiranja (+), i budući da operator koji spaja levu i desnu stranu izraza (/), ima viši prioritet - prvo je potrebno levu stranu izraza uokviriti zagradama ....
.... nakon čega se može formirati infiksni izraz (a + b * c) / d - koji odgovara stablu:
Računanje vrednosti izraza preko stabla
Pri računanju vrednosti izraza, potrebno je pre svega zameniti identifikatore (promenljivih), brojčanim vrednostima.
Za primer ćemo uzeti sledeće vrednosti:
- a = 6
- b = 3
- c = 4
- d = 2
Sama procedura računanja vrednosti podrazumeva postorder obilazak stabla, pri čemu se operacija zapisana u određenom čvoru, primenjuje na levo i desno podstablo operatora - onda kada dati operator dođe na red za izvršavanje - posle čega na ("doatadašnjem") mestu operatora ostaje izračunata vrednost.
Pogledajmo kako algoritam za računanje vrednosti funkcioniše na primeru stabla koje smo do sada koristili ....
U postorder obilasku stabla, biće za početak preskočeni operatori deljenja i sabiranja (jer podstabla navedenih operatora nisu rešena), a poslednji operator na koji se nailazi preko "prve grane DFS obilaska" (operator množenja) - praktično je prvi operator koji se uzima u obzir za računanje.
Kada se obavi operacija koja odgovara čvoru * (3 * 4) ...
.... podstablo 3 * 4 se svodi na izračunatu vrednost (12):
Sledeći po redu čvor sa operatorom (operator sabiranja) ....
.... svodi se na rezultat izvršavanja operacije 6 + 12 (18):
Na kraju, jedini preostali čvor koji predstavlja operaciju (operator deljenja) ....
.... takođe se svodi na vrednost operacije (18 / 2 = 9).
Rezultat računanja vrednosti izraza je vrednost koja je zapisana u korenom čvoru:
Još jednom, spomenimo da je u implementaciji (tj. pri projektovanju klase koja predstavlja čvorove), potrebno predvideti polje koje će sadržati vrednost izraza koji odgovara čvoru, jer (u najvećem broju situacija), doslovno "urušavanje" stabla u jedan čvor - ne predstavlja elegantno rešenje.
Generator stabla izraza
Pred kraj, pružamo vam priliku da isprobate 'tehnikalije' o kojima smo pisali u članku: unesite infiksni izraz i pustite da program generiše stablo izraza i sva tri oblika notacije.
Dozvoljeni znakovi:
- pojedinačna mala i velika slova engleskog alfabeta
- znaci računskih operacija:
+,-,*,/ - zagrade
Stablo izraza:
Za kraj ....
Rekli bismo da hrabrim pojedincima koji su stigli do kraja ovog članka, pri čemu nisu preskakali nijedan deo i zapravo žele da dodatno istražuju tematiku, preostaje samo još jedan zadatak - samostalna implementacija stabla izraza.
Nije baš u pitanju "lagan" zadatak, ali, celokupno iskustvo je (zapravo) prilično zabavno - a usput ćete mnogo toga i naučiti.
Samo hrabro! :)