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 koristićemo stek
- tokenima koji predstavljaju operande (tj. promenljive), pripisaćemo 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 - kao novi operand)
- 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 = 2
.... 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 znači da 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 računanje vrednosti izraza 5 - 1 završeno, 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 2) ....
.... 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 deljenja) ....
.... 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.
Implementacija metode za računanje vrednosti postfiksnog izraza
Sada kada razumemo algoritam za računanje vrednosti izraza u postfiksnoj notaciji, pogledajmo i implementaciju:
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)) ....