Shunting Yard - Implementacija - 2. deo - Računanje vrednosti postfiksnog izraza
Uvod
U drugom članku o implementaciji algoritma Shunting Yard bavićemo se delom algoritma koji se tiče računanja vrednosti postfiksnog izraza (koji je prethodno dobijen pretvaranjem infiksnog izraza, preko postupka koji smo opisali u prethodnom nastavku - ili je jednostavno u pitanju izraz koji je neposredno zapisan u postfiksnom obliku).
I ovoga puta, u pitanju je algoritam linearne složenosti, koji se može implementirati na jednostavan način ....
Algoritam
Pošto smo se sa postupkom za računanje vrednosti postfiksnog izraza upoznali još u uvodnom članku, ovoga puta se nećemo previše baviti teorijom i odmah ćemo preći na praktični deo, pri čemu ćemo za primer koristiti sledeći izraz ....
a * (b - c) - d
.... koji, posle prebacivanja u postfiksnu notaciju, ima sledeći oblik:
abc-*d-
Nekoliko smernica za početak:
- za privremeni smeštaj tokena biće korišćen stek
- tokenima koji predstavljaju operande (tj. promenljive), biće pripisane konkretne vrednosti
Pre nego što tokenima pripišemo brojčane vrednosti, sagledaćemo ukratko šematski prikaz struktura koje učestvuju u računanju vrednosti (posle čega ćemo predstaviti algoritam za računanje):
Postupak za računanje vrednosti postfiksnog izraza (poznat od ranije i ovoga puta uobličen u algoritam), sastoji se iz sledećih koraka:
- tokeni iz reda za čekanje, * obrađuju se jedan za drugim
- ukoliko se iz reda preuzima operand (tj. promenljiva), token se smešta direktno na vrh steka
-
ukoliko se iz reda preuzima operator (koji se pri tom uklanja iz reda), sledi računanje vrednosti izraza koji odgovara operatoru (i postavljanje rezultata na stek):
- sa vrha steka se preuzimaju (i praktično uklanjaju), dva operanda
- operandi se privremeno smeštaju na pomoćne lokacije, pri čemu se vodi računa o redosledu **
- obavlja se operacija (uz pamćenje rezultata operacije)
- na stek se vraća rezultat operacije (praktično - u vidu novog operanda)
- posle obrade svih tokena iz reda za čekanje, token koji stoji na vrhu steka - predstavlja krajnji rezultat
Pogledajmo, preko konkretnog primera, kako algoritam funkcioniše u praksi.
Praktičan primer
Kao što smo već nagovestili, jasno je da se vrednost izraza ne može izračunati ukoliko u izrazu ostanu apstraktne slovne oznake za operande (tj. identifikatori promenljivih), i stoga je prvo potrebno da se tokeni sa identifikatorima zamene tokenima koji predstavljaju konkretne brojčane vrednosti.
Tokeni a, b, c i d biće povezani sa sledećim vrednostima:
- a = 2
- b = 5
- c = 1
- d = 3
.... nakon čega se može pristupiti računanju vrednosti izraza.
Prvi token (koji predstavlja operand) ....
.... smešta se na stek:
Drugi token (5), takođe operand ....
.... takođe se smešta direktno na stek:
Isto važi i za treći token ....
.... (operand 1 se smešta na stek):
Četvrti token (-) ....
.... predstavlja znak operacije, što podrazumeva drugačiji vid obrade: sledi računanje vrednosti 'podizraza' (koji obuhvata jedan operator i dva operanda).
Sa steka se uklanjaju dva gornja elementa ....
.... i prebacuju se na pomoćne lokacije za obradu:
Pošto su tokeni prebačeni na pomoćne lokacije, računa se vrednost izraza ....
.... posle čega se rezultat vraća nazad na stek:
Pošto je obrada izraza 5 - 1 završena, nastavlja se obrada tokena iz reda za čekanje - i ponovo nailazimo na znak operacije:
I ovoga puta, potrebno je operator upariti * sa dva gornja elementa sa steka:
Tokeni se smeštaju na pomoćne memorijske lokacije ....
.... obavlja se operacija množenja ....
.... a rezultat se vraća nazad na stek:
Šesti token (operand 3) ....
.... smešta se na stek:
Sedmi token (-), predstavlja znak operacije ....
.... što znači da ponovo sledi postupak za računanje vrednosti podizraza.
Sa steka se uklanjaju dva operanda (koji ovoga puta odgovaraju operaciji oduzimanja) ....
.... tokeni se smeštaju na pomoćne memorijske lokacije .....
.... računa se vrednost izraza ....
.... nakon čega se rezultat smešta na stek:
Budući da u redu za čekanje nema više tokena, izraz je rešen ....
.... a rezultat je vrednost sa vrha steka.
Pronalaženje grešaka
Kao što smo najavili još u 1. nastavku, razmotrićemo i metode za pronalaženje grešaka u izrazima.
Različite greške moguće je ustanoviti u različitim fazama tumačenja izraza:
- greške u uparivanju zagrada mogu se ustanoviti u prvom prolasku (tokom obrade infiksnog izraza)
- greške u uparivanju operanada i operatora (višak ili manjak operanada i/ili operatora), mogu se ustanoviti tokom računanja vrednosti postfiksnog izraza
Slede primeri ....
Nedostajuća zatvorena zagrada
U infiksnom izrazu ....
a * (b + c
.... nedostaje zatvorena zagrada.
Tokom interpretacije izraza (u 'prvom prolasku'), nastaje sledeće stanje kontrolnih struktura:
RED: [ a b c ]
STEK: [ * ( + ]
Kada algoritam stigne do poslednjeg tokena, sledi prebacivanje tokena sa steka u red, ali - pošto algoritam (u toku prebacivanja) nailazi na otvorenu zagradu - u pitanju je greška.
Nedostajuća otvorena zagrada
U infiksnom izrazu ....
a + b * c)
.... nedostaje otvorena zagrada.
Tokom interpretacije izraza (u 'prvom prolasku'), nastaje sledeće stanje kontrolnih struktura:
RED: [ a b c ]
STEK: [ + * ]
Kada algoritam stigne do poslednjeg tokena - koji predstavlja zatvorenu zagradu, sledi prebacivanje tokena sa steka u red, ali - pošto algoritam ne nailazi na otvorenu zagradu (na steku) - u pitanju je greška.
Višak operatora
U infiksnom izrazu ....
a + b +
.... postoji višak operatora.
Nakon prvog prolaska (i pošto su operandi a i b zamenjeni npr. vrednostima 10 i 15), red za čekanje ima sledeći sadržaj:
RED: [ 10 15 + + ]
STEK: [ ]
Nakon prvog računanja vrednosti ....
RED: [ + + ]
STEK: [ 10 15 ]
.... nastaje sledeća situacija:
RED: [ 25 + ]
STEK: [ ]
U narednom koraku, operand 25 se može smestiti na stek, ali, budući da bi nakon toga usledila operacija sabiranja - a pri tom je na steku prisutan samo jedan operand - u pitanju je greška.
Višak operanada
U infiksnom izrazu ....
a + b c
.... postoji višak operanada (tj. manjak operatora).
Nakon prvog prolaska (i pošto su operandi a, b i c zamenjeni vrednostima 10, 15 i 20), red za čekanje ima sledeći sadržaj:
RED: [ 10 15 20 + ]
STEK: [ ]
Nakon prvog računanja vrednosti ....
RED: [ + ]
STEK: [ 10 15 20 ]
.... nastaje sledeća situacija:
RED: [ ]
STEK: [ 10 35 ]
U narednom koraku, "trebalo bi" da postoji operator koji bi pokrenuo uklanjanje operanada sa steka (i računanje vrednosti podizraza), ali, pošto takav operator ne postoji - u pitanju je greška.
Implementacija metode za računanje vrednosti postfiksnog izraza
Pošto smo se upoznali sa algoritmom za računanje vrednosti izraza, prikazaćemo i programski kod: *
private void RacunanjeVrednosti(Queue<char> red)
{
Stack<Double> stek = new Stack<Double>();
char[] tokeni = red.ToArray();
Int32 i, d = tokeni.Length;
for (i = 0; i < d;i++ )
{
char znak = tokeni[i];
if (znak >= 97 && znak <= 122)
{
switch (znak)
{
case 'a': stek.Push(var_a); break;
case 'b': stek.Push(var_b); break;
case 'c': stek.Push(var_c); break;
case 'd': stek.Push(var_d); break;
case 'e': stek.Push(var_e); break;
default: MessageBox.Show("Uneli ste neodgovarajuću promenljivu!"); return;
}
}
else
{
Double Op2 = stek.Pop(), Op1 = stek.Pop();
switch (znak)
{
case '+': stek.Push(Op1 + Op2); break;
case '-': stek.Push(Op1 - Op2); break;
case '*': stek.Push(Op1 * Op2); break;
case '/': stek.Push(Op1 / Op2); break;
default: break;
}
}
}
Double rez = stek.Pop();
label9.Text = rez.ToString();
}
Vidimo da implementacija nije komplikovana ni u slučaju algoritma za računanje vrednosti izraza (naprotiv, reklo bi se čak da je znatno jednostavnija u odnosu na algoritam za prebacivanje izraza iz infiksne notacije u postfiksnu), i takođe se može primetiti da je složenost algoritma ponovo O(n), to jest, svaki token ponovo se rešava "u mestu".
Za kraj ....
U dva članka koje smo posvetili implementaciji algoritma Shunting Yard, nismo (zarad preglednosti) koristili sveobuhvatnije tokene (slogove ili objekte klase, koji omogućavaju da se skladište: i promenljive, i brojčane vrednosti), međutim - verujemo da će čitaoci biti u stanju da samostalno implementiraju takve tokene.
(Naravno, toplo preporučujemo da pokušate. :))
Takođe, pripremamo i članak o stablima izraza - strukturama koje nastaju preko algoritma Shunting Yard, predstavljaju izraz u apstraktnom smislu, i omogućavaju računanje vrednosti i pretvaranje strukture stabla u bilo koji oblik notacije (očekujte članak uskoro) ....