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), a uvod u nešto kompleksniju strukturu sintaksnih stabala biće č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 upoznali smo okvirno 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 su sa listovima koji predstavljaju operande, a takođe je jasno da operand (tj. broj ili promenljiva), u stablu izraza može predstavljati samo 'list'.
Postorder obilazak unutrašnjeg stabla operatora određuje redosled izvršavanja operacija, i stoga: 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 ili postfiksni zapis izraza.
Pretvaranje infiksnog izraza u stablo izraza
Iako postoje i druge opcije, stabla izraza najčešće nastaju: ili pretvaranjem infiksnog izraza u stablo izraza, ili pretvaranjem 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 zadati 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 jednostavnija.
Struktura podataka preko koje se može referencirati celo stablo, u osnovnom (tehničkom) smislu je zapravo običan pokazivač (ili 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 (operator), 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).
Pravila za pretvaranje infiksnog izraza u stablo izraza
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 od 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 se vodi 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
Primer pretvaranja infiksnog izraza u stablo izraza
Za upoznavanje sa postupkom pretvaranja infiksnog izraza u stablo izraza, koristićemo sledeći jednostavni infiksni izraz ....
(a + b * c) / d
.... koji odgovara stablu sa slike #1.
Na početku, elemente izraza prvo treba pretvoriti u tokene i smestiti u red za čekanje ....
.... nakon čega sledi obrada 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. *
U nastavku, pretposlednji operand, token c ....
.... prebacuje se na stek sa stablima ....
.... nakon čega algoritam nailazi na zatvorenu zagradu:
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 ....
.... a 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. *
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 se stablo 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 se nalazi na vrhu steka.
Pretvaranje postfiksnog izraza u stablo izraza
Za pretvaranje postfiksnog izraza u stablo izraza, postupak je još jednostavniji (kao što smo već nagovestili), i pri tom se kao pomoćna struktura podataka koristi samo jedan stek.
Pravila za pretvaranje postfiksnog izraza u stablo izraza
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 vidu stabla sa jednim čvorom
- ako je token koji se preuzima i uklanja iz reda - operator, sledi postupak koji podrazumeva da se sa steka uklanjaju gornja dva stabla nakon čega 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 i konkretan 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:
Pojava operatora množenja (sledećeg tokena po redu) ....
.... praktično pokreće kreiranje podstabla, što znači da se operator uparuje 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, a kao što smo naveli još na početku, preko formiranog stabla izraza moguće je rekonstruisati sva tri oblika notacije (sprovođenjem DFS obilazaka), i moguće je naravno izračunati vrednost izraza.
U nastavku, detaljno ćemo prikazati navedene postupke.
Kreiranje prefiksnog zapisa preko stabla izraza
Prefiksni zapis izraza nastaje preorder obilaskom stabla, pri čemu za svaki čvor važi sledeći redosled ispisa:
- koreni čvor
- levo podstablo
- desno podstablo
U primerima ćemo koristiti stablo koje je nastalo preko jednog od dva prethodno prikazana postupka za kreiranje stabla izraza:
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), takođe se može 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, * sledi povratak na koreni čvor, ali, pošto je koreni čvor rešen (odavno :)) - i pri tom nema čvorova koji se dalje mogu obilaziti - prefiksni izraz je formiran:
Kreiranje infiksnog zapisa preko stabla izraza
Infiksni zapis izraza nastaje inorder obilaskom stabla, ali (sasvim očekivano), nije u pitanju isti ispis kao u slučaju tipičnog/standardnog inorder obilaska (sa kakvim smo se sreli u 3. nastavku mini-serijala o AVL implementaciji).
Da bismo dobili korektan rezultat (pri formiranju bilo kog 'podizraza' koji odgovara nekom podstablu), pažnju treba obratiti na prioritet tri čvora: operatora koji stoji u korenu podstabla, i dva direktna potomka.
Za početak, osnovna postavka je (zapravo) slična tipičnom/uobičajenom inorder obilasku:
Prvo se rešava i ispisuje levo podstablo (u konkretnom primeru: (a+b*c)), zatim se ispisuje znak operacije (/), nakon čega se ispisuje i sadržaj desnog podstabla (tj. čvor d).
Naravno, jedno od najvažnijih pitanja (na neki način - najvažnije pitanje (kako u ovom primeru tako i inače)), tiče se postavljanja zagrada.
Prethodno smo naveli sadržaj levog podstabla u zagradi ('kako i treba'), što je bila dobra ilustracija, ali (pošto stabla nećemo rešavati "mi", već računar), moramo iznaći algoritam koji je u stanju da donosi pravilne i blagovremene odluke o uokviravanju delova izraza zagradama.
Pre nego što pređemo na opis algoritma, primetićemo sledeće:
- ne računajući zagrade, redosled tokena (u ispisu), odgovara tipičnom/standardnom inorder ispisu binarnog stabla
- pri uokviravanju delova izraza zagradama, u obzir treba uzeti prioritete: levog podstabla, znaka operacije i desnog podstabla
- prioritet bilo kog podstabla (tj. kasnije, bilo kog pravilno definisanog infiksnog podizraza), određen je prioritetom operacije koja stoji u korenu podstabla
Prisustvo ili odsustvo zagrada (u ispisu), određuje se na pomalo idiosinkratičan način - u trenutku kada se u obilasku nailazi na koren podstabla:
- leva strana izraza uokviruje se naknadno
- desna strana izraza uokviruje se unapred
Što se tiče prioriteta izraza, uvešćemo sledeća pravila:
- samostalni operandi imaju prioritet 0
- stabla izraza u čijem su korenu operacije sabiranja ili oduzimanja, imaju prioritet 1
- stabla izraza u čijem su korenu operacije množenja ili deljenja, imaju prioritet 2
U slučaju stabla koje koristimo kao primer, prvo se rešava levo podstablo:
Operand a (tj. samostalni operand), neće biti uokviren zagradama, ali, pitanje je da li treba uokviriti izraz b*c?
Algoritam je sledeći: u svakom podstablu, leva ili desna strana izraza uokviruje se zagradama ukoliko je prioritet operacije u vrhu levog ili desnog podstabla - veći od nule - i pri tom manji od prioriteta operacije koja je zapisana u korenom čvoru.
Pošto operator * (iz desnog podstabla b*c) ima veći prioritet od operatora + koji stoji u korenu podstabla a+b*c, sledi da podizraz b*c neće biti uokviren zagradama.
U svakom slučaju, levom podstablu početnog stabla odgovara zapis a + 'sadržaj desnog podstabla' (bez uokviravanja zagradama):
Pošto smo 'poslednje podstablo' rešili još davno ('u mislima'), preostaje da primetimo (ovoga puta 'zvanično'), da je u pitanju zapis b*c (naravno, bez zagrada): *
Levom podstablu početnog izraza odgovara infiksni izraz a+b*c (koji je 'i dalje' * bez zagrada):
Kada se vratimo na rešavanje glavnog stabla, susrećemo se situacijom u kojoj se leva strana izraza uokviruje zagradama - 'naknadno'. *
Početnom stablu odgovaraju sledeći delovi:
- leva strana, sa izrazom
a + b * c(čiji je prioritet 1) - znak operacije
/(čiji je prioritet 2) - desna strana, sa izrazom
d(čiji je prioritet 0)
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 veći prioritet - prvo je potrebno levu stranu izraza uokviriti zagradama ....
.... nakon čega se može formirati infiksni izraz (a + b * c) / d - koji odgovara početnom stablu:
Kreiranje postfiksnog zapisa preko stabla izraza
Postfiksni zapis izraza nastaje postorder obilaskom stabla, pri čemu za svaki čvor važi sledeći redosled ispisivanja:
- levo podstablo
- desno podstablo
- koreni čvor
Ponovo koristimo isto stablo, pretraga ponovo počinje od korenog čvora, ali, koreni čvor se praktično preskače * u prvom koraku:
Kao što smo nagovestili, operator sabiranja takođe neće biti ispisan u prvom koraku, jer još uvek nije ispisan ostatak stabla 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 ovog čvora:
Sledi prelazak na desno podstablo, u čijem korenu stoji operator množenja - koji se takođe ne može ispisati 'odmah' (ni u slučaju čvora * nije obiđen (tj. ispisan) ostatak stabla 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 (a vidimo takođe, na slici, 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 nema naravno daljeg grananja):
Sada se može ispisati i operator množenja (budući da su obiđena oba podstabla) ....
.... a isto važi i za operator sabiranja (obiđena su oba podstabla i čvor + se može ispisati):
Međutim, po povratku na koren početnog stabla, može se samo konstatovati da ('i dalje') nije vreme za ispis čvora /, jer nije obrađeno desno podstablo ....
.... ali, u ovom slučaju podstablo će biti rešeno vrlo brzo - operand d je list i može se ispisati već u sledećem koraku ....
... 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:
Alternativni algoritam za kreiranje infiksnog zapisa
Alternativni algoritam za kreiranje infiksnog zapisa predstavlja svojevrsnu kombinaciju inorder i postorder algoritama: prvo se obavlja postorder obilazak, ali, ispis odgovara inorder obilasku (naravno, i ovoga puta, uz dodavanje zagrada na odgovarajućim mestima).
Procedura koja se odnosi na određeno podstablo (u čijem je korenu token koji predstavlja operaciju), sastoji se iz sledećih pojedinačnih koraka:
- 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 infiksnog zapisa (koji odgovara datom podstablu)
Poslednji korak podrazumeva umetanje odgovarajućeg znaka operacije između rezultata za levo i desno podstablo, * uz potencijalno dodavanje zagrada ** izrazima koji su nastali rešavanjem levog i/ili desnog podstabla.
U konkretnom primeru koji razmatramo ....
.... prvo se rešava levo podstablo (crveni deo), zatim desno podstablo (plavi deo), a nakon što se završe obe operacije, rešeni delovi se spajaju 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
Baš kao i u prvom algoritmu za kreiranje infiksnog ispisa, 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), iz čega sledi da se celo levo podstablo početnog izraza može zapisati bez zagrada (tj. bez dodavanja zagrada podizrazu b * c):
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).
Kao i prvi put kada smo se bavili kreiranjem infiksnog zapisa, u 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)
Shodno tome što operator + (koji stoji u korenu levog podstabla), ima niži prioritet od operatora * (koji stoji u korenu početnog stabla), potrebno je levu stranu početnog 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 da identifikatori (promenljivih) budu zamenjeni brojčanim vrednostima.
U slučaju stabla koje smo do sada koristili kao primer, uvešćemo 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 ("dotadaš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.
Nakon obavljanja operacije 3 * 4 koja odgovara čvoru * ....
.... podstablo 3 * 4 se svodi na izračunatu vrednost 12:
Sledeći po redu čvor sa operatorom (operator sabiranja) ....
.... svodi se na rezultat 18, koji odgovara izvršavanju operacije 6 + 12:
Na kraju, jedini preostali čvor koji predstavlja operaciju (tj. čvor koji stoji u podstablu izraza 18 / 2) ....
.... takođe se svodi na izračunatu vrednost, u ovom slučaju: 9.
Vrednost koja je (na kraju) zapisana u korenom čvoru, predstavlja rezultat računanja vrednosti (početnog) izraza. *
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 ....
Posle svega što smo prikazali, može se reći 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" ili "jednostavan" zadatak, ali, celokupno iskustvo je (zapravo) prilično zabavno - a usput ćete mnogo toga i naučiti.
Samo hrabro! :)