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 ćemo se upoznati sa time kako se ranije opisani algoritam za računanje može implementirati na računarima, a nakon toga ćemo razmotriti i jedan praktičan primer, to jest sledeći infiksni izraz ....
a * (b - c) - d
.... koji, posle prebacivanja u postfiksnu notaciju, ima sledeći oblik:
abc-*d-
Pri računanju vrednosti postfiksnog izraza, koriste se dve strukture podataka:
- red za čekanje, sa tokenima koji predstavljaju postfiksni izraz *
- pomoćni stek
Kada smo prvi put u prethodnom članku prikazali sličnu "šemu", osvrnuli smo se na "moguće putanje", međutim, ovoga puta postoji jedna putanja: tokeni iz reda za čekanje (koji je popunjen u prvoj etapi, i koji praktično predstavlja postfiksni izraz), mogu prelaziti (samo) na stek, a što se tiče ostalih pomoćnih struktura koje vidimo na slici - sledi objašnjenje (u okviru opisa postupka za računanje).
Pravila za premeštanje tokena
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 (sleva nadesno)
- 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, vrednost izraza se 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 brojčane vrednosti koje odgovaraju identifikatorima.
U konkretnom primeru, smatraćemo da tokenima a, b, c i d odgovaraju sledeće celobrojne vrednosti:
- a = 2
- b = 5
- c = 1
- d = 3
Za razliku od postupka za 'razvrstavanje tokene' (iz prošlog članka), ovoga puta postoji jedna putanja za tokene koji izlaze iz reda za čekanje, ali (naravno/očekivano), postoji razlika u tome gde i kako tokeni završavaju:
- operandi se prebacuju direktno na stek
- operatori se ne prebacuju na stek, ali, pojava operatora pokreće postupak za računanje vrednosti podizraza (koji odgovara operatoru koji se trenutno razmatra)
Prvi token iz reda za čekanje (operand 2) ....
.... 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 ....
.... a 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 (5) smešta na stek:
Budući da u redu za čekanje nema više tokena, izraz je rešen ....
.... a krajnji rezultat je vrednost na vrhu 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) ....