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 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 ....
Računanje vrednosti postfiksnog izraza - 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
Tokeni a, b, c i d biće povezani sa sledećim vrednostima:
- a = 2
- b = 5
- c = 1
- d = 2
Sam postupak za rešavanje (poznat od ranije i ovoga puta uobličen u algoritam), sastoji se iz sledećih koraka:
- tokeni iz liste obrađuju se jedan za drugim
- ukoliko se iz liste tokena preuzima operand (tj. promenljiva), token se smešta direktno na vrh steka
-
ukoliko se iz liste tokena preuzima operator (koji se pri tom uklanja iz liste), sledi računanje vrednosti izraza koji odgovara operatoru (i postavljanje rezultata na stek):
- sa vrha steka se preuzimaju (i praktično uklanjaju), dva operanda, pri čemu se vodi računa o njihovom 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 liste, token koji stoji na vrhu steka - predstavlja krajnji rezultat
Pogledajmo, preko konkretnog primera, kako algoritam funkcioniše u praksi.
Primer računanja vrednosti izraza
Za početak (kao što smo već nagovestili), potrebno je da se tokeni sa identifikatorima ....
.... zamene tokenima koji predstavljaju konkretne brojčane vrednosti:
.... posle č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, i stoga je potrebno sa steka skinuti dva elementa ....
.... i prebaciti ih 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 osnovne liste - 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 listi nema više tokena, izraz je rešen ....
.... a rezultat je vrednost sa vrha steka.
Računanje vrednosti izraza u postfiksnoj notaciji - Implementacija
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)) ....