Približna specifikacija:
Code:
cifra ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
broj ::= cifra+
izraz ::= broj
izraz ::= izraz "+" izraz |
izraz "-" izraz |
izraz "/" izraz |
izraz "*" izraz |
"(" izraz ")"
1. Izvršiš ,,tokenizaciju'' izraza "50*4-8/8" i dobiješ:
Code:
50[iz] *[op] 4[iz] -[op] 8[iz] /[op] 8[iz]
Ovde ako si imao zagrade, od toga ćeš praviti jedan izraz.
2. Nađeš sve *[op] i /[op] (prioritetne operacije), i sa njima susednim tokenima kategorije [iz] napraviš stabla, gde rekurzivno obrađuješ svaki izraz ([iz])
3. Isto za ostale operacije (+[op] i -[op])
Neoptimizovan ,,pseudo-srpski'' kod:
Code:
ListaTokena=tokenize("50*4-8/8")
praviStablo(ListaTokena):
za svako i, ListaTokena(i)==*[op] ili ListaTokena(i)==/[op]:
Prethodnik = ListaTokena(i-1)
Sledbenik = ListaTokena(i+1)
Izraz = praviStablo(Prethodnik), ListaTokena(i), praviStablo(Sledbenik)
Zameni(ListaTokena(i-1,i,i+1) sa Izraz) # Izbaci prethodnika i sledbenika, a na mesto i stavi Izraz
za operacije +[op] i -[op], radi isto kao gore # razdvojeno zbog prioriteta
praviStablo(ListaTokena) # dok god ListaTokena ne postane jedan Izraz,
# ponavljaj i ponavljaj
Rekurzija je gore potrebna samo za unete složene izraze (one u zagradama); ako ne dozvoliš zagrade, moglo bi i bez rekurzije.
Primeri kako radi algoritam (po jedna iteracija u jednom redu) za dva izraza:
Code:
10/5/6*7
-> 10[iz] /[op] 5[iz] /[op] 6[iz] *[op] 7[iz]
-> (10/5)[iz] /[op] 6[iz] *[op] 7[iz]
-> ((10/5)/6)[iz] *[op] 7[iz]
-> (((10/5)/6)*7)[iz]
50*4-8/8
-> 50[iz] *[op] 4[iz] -[op] 8[iz] /[op] 8[iz]
-> (50*4)[iz] -[op] (8/8)[iz]
-> ((50*4)-(8/8))[iz]
Što se praktičnih stvari tiče, ima tu još poneka začkoljica (npr. provera da li su Prethodnik i Sledbenik zaista kategorije [iz]; ispunjavanje uslova da je u ListaTokena moguće smestiti i stablo kakvo je vraćeno u Izraz, popravka vrednosti i, itd.), ali neću valjda sve da ja ispišem u ovom
lako razumljivom pseudo-jeziku.
Naravno, drugi način ti je da izvršiš ,,normalizaciju'' izraza: umetneš zagrade tamo gde su neophodne, a onda je
veoma lako napraviti stablo. Postupak je sličan kao i gore, samo ne praviš stablo odmah, već umećeš zagrade.
Tako za izraz "50*4-8/8" potražiš sve * i /, prve susedne izraze uokviriš zagradama, i dobiješ "(50*4)-(8/8)". Ponoviš isto za + i -, i eto ti ga "((50*4)-(8/8))". A koliko je dalje trivijalno, valjda ne treba ni da pričam.
Toliko
Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.