Shunting Yard - Implementacija - 1. deo - Prevođenje izraza iz infiksnog zapisa u postfiksni
Uvod
U uvodnom članku o postfiksnoj notaciji pisali smo o tome koliki značaj i upotrebnu vrednost postfiksni zapis ima u tumačenju algebarskih izraza na računarima, međutim, postupak za transformaciju izraza koji smo prikazali na kraju (iako sam po sebi informativan), u velikoj meri je proizvoljan i svojstven samo ljudskom načinu razmišljanja, i stoga je ostalo da prodiskutujemo o (zvaničnom) algoritamskom postupku za pretvaranje infiksnih izraza u postfiksne ....
Kratko podsećanje
Za sam početak, nekoliko osnovnih smernica sa kojima smo se već upoznali:
- infiksna notacija nije optimalan način za zapisivanje algebarskih izraza na računarima (podsetićemo se ispod na konkretne razloge)
- nedostatak efikasnijeg rešenja, neko vreme je praktično sputavao početak razvoja računarske industrije
- problem je rešen 1961, kada je Edzger Dajkstra (holandski naučnik svetskog glasa), objavio članak sa opisom algoritma za računanje vrednosti algebarskih izraza, koji je zasnovan na tzv. Obrnutoj poljskoj ("postfiksnoj") notaciji *
Kao što smo videli u uvodnom članku, pri proceni vrednosti infiksnih izraza (u kojima se pojavljuju operatori različitih prioriteta), glavni problem tiče se nedostatka informacije o ("pravom") ** prioritetu operatora koji se u određenom trenutku razmatra, što onemogućava rešavanje izraza u 'jednom prolasku'.
Rešenje koje smo prikazali (u članku o postfiksnoj notaciji), praktično je podrazumevalo svođenje infiksnog izraza na postfiksni oblik - uz korišćenje stabla koje smo konstruisali po ugledu na početni (infiksni) izraz, ali, budući da računari ne mogu (u praktičnom smislu), koristiti stabla izraza zarad početnog utvrđivanja prioriteta operacija (budući da takva stabla ne nastaju u memoriji "sama od sebe"), *** potrebno je primeniti drugačiji postupak ....
Algoritam Shunting Yard
Shunting Yard je algoritam linearne složenosti, preko koga se infiksni izraz prvo svodi na 'posrednički oblik', ** nakon čega tipično sledi postupak računanja vrednosti:
- u prvom prolasku (kroz infiksni izraz), kreira se postfiksni zapis ili stablo izraza **
- u drugoj etapi, računa se vrednost izraza (prolaskom kroz izraz u postfiksnoj notaciji, ili, postorder obilaskom stabla izraza)
Pri prevođenju infiksnog izraza u postfiksni, koriste se tri strukture podataka:
- lista tokena (čiji su elementi poređani tako da predstavljaju početni (infiksni) izraz)
- stek za operatore (preko koga se operatori iz ulaznog izraza razvrstavaju shodno prioritetu)
- red za čekanje (u koji se smeštaju tokeni koji su u potpunosti obrađeni)
Moguće putanje tokena su sledeće:
- operandi iz liste mogu se prebacivati samo u red za čekanje
- operatori iz liste mogu se prebacivati samo na stek ("sporedni kolosek") :)
- operatori sa steka mogu se prebacivati samo u red za čekanje
Algoritam podrazumeva da se svi tokeni (celine u izrazu, od kojih svaka predstavlja pojedinačni operand ili operator), premeste iz osnovne liste tokena - u red za čekanje.
Sadržaj reda za čekanje, na kraju predstavlja izraz u postfiksnoj notaciji - i sve se obavlja u jednom prolasku kroz izraz.
Pravila za premeštanje tokena
Premeštanje tokena, iz (početne) liste tokena - u red za čekanje (koji predstavlja postfiksni izraz), obavlja se prema sledećim pravilima:
- ukoliko je iz liste preuzet token koji predstavlja operand, navedeni token se direktno prebacuje u red za čekanje
- ukoliko je iz liste preuzet token koji predstavlja operator (jedan od znakova operacije ili zagradu), navedeni token se postavlja na stek, prema sledećim pravilima:
- ukoliko je stek prazan ili je na vrhu steka otvorena zagrada, bilo koji operator iz liste (osim zatvorene zagrade), direktno se smešta na vrh steka
- ukoliko je iz liste preuzeta otvorena zagrada, token
(se takođe smešta direktno na vrh steka (bez obzira na prethodni sadržaj steka) - ukoliko je iz liste preuzet token
+ili-, a na vrhu steka je operator istog ili višeg prioriteta, prvo se operator sa vrha steka prosleđuje u red za čekanje, i tek onda se operator preuzet iz liste tokena smešta na vrh steka (osim u slučaju koji sledi odmah ispod) - ukoliko je u prethodnoj situaciji (kada se iz osnovne liste preuzima
+ili-), u red za čekanje prvo prebačen operator*ili/sa vrha steka - posle čega se na vrhu steka pojavio operator+ili-(ubačen u nekom od ranijih koraka) - potrebno je u red prebaciti i taj (drugi) token sa vrha steka (operator+ili-), pre nego što se na vrh steka smesti token+ili-koji se preuzima iz liste - ukoliko se iz liste preuzima token
*ili/, a na vrhu steka je operator nižeg prioriteta (+ili-), operator iz liste se stavlja na stek direktno (upravo je to razlog zašto se u prethodnom koraku, ispod operatora*ili/, mogao naći operator+ili-) - ukoliko se iz liste preuzima token
*ili/, a na vrhu steka je operator istog prioriteta, prvo se operator sa vrha steka prosleđuje u red za čekanje, posle čega se operator preuzet iz liste smešta na vrh steka - ukoliko se iz liste tokena preuzme operator
)(zatvorena zagrada), sama zatvorena zagrada se zanemaruje, a operatori sa steka se premeštaju redom (jedan po jedan), iz steka - u red za čekanje, sve dok na vrhu steka ne ostane otvorena zagrada - posle čega se otvorena zagrada takođe uklanja sa vrha steka (ali, ne premešta se u red)
Kada se lista tokena isprazni, proverava se stek i važe sledeća pravila:
- ukoliko je stek prazan, izraz je rešen
- ukoliko stek nije prazan, operatori sa steka se premeštaju redom (jedan po jedan), iz steka - u red za čekanje - nakon čega je izraz rešen
Korišćenjem pravila koja smo naveli, svaki token iz liste tokena (koji dospe na obradu), rešava se odmah i ne vraća se nazad u listu - čime se postiže linearna složenost algoritma.
Pravila koja smo naveli mogu delovati komplikovano za početak, ali, zapravo je u pitanju vrlo intuitivan algoritam i dovoljno je samo proći kroz izvestan broj izraza (posle čega verujemo da će čitaocima sva pravila postati jasna u potpunosti).
U tom smislu, razmotrićemo dva primera: * jednostavan izraz bez zagrada, i izraz sa zagradama (koji obuhvata većinu navedenih pravila).
Primer #1 - Jednostavan izraz bez zagrada
U prvom primeru koristićemo sledeći početni infiksni izraz:
a + b * c
Prvi token predstavlja operand (promenljivu ili brojčanu vrednost) ....
.... i shodno pravilima, premešta se direktno u red.
Sledeći token (operator +) ....
.... postavlja se na vrh steka (koji je prethodno bio prazan):
Treći token (operand b) ....
.... direktno se prosleđuje u red:
Operator množenja ....
.... može se postaviti na vrh steka (shodno pravilima), s obzirom na to da operator koji je već na vrhu steka (+), ima niži prioritet:
Operand c ....
.... direktno se prosleđuje u red:
Lista tokena je sada prazna i - kada bi i stek bio prazan - izraz bi bio rešen.
Međutim, pošto u ovom slučaju stek nije prazan, potrebno je da tokeni iz steka budu premešteni u red za čekanje.
Prvi na redu je operator sa vrha steka, operator * ....
.... koji se u sledećem koraku premešta na kraj reda ....
.... posle čega ostaje operator sabiranja + ....
.... koji se takođe premešta u red ....
Posle svih operacija, lista tokena je potrošena, stek je prazan ....
.... što znači da je izraz rešen.
Primer #2 - Složeniji izraz sa zagradama
U drugom primeru, prebacićemo u postfiksnu notaciju sledeći infiksni izraz:
a * (b + c - d).
Prvi token (operand) ....
.... direktno se prosleđuje u red za čekanje:
Operator množenja ....
.... postavlja se na prazan stek:
Otvorena zagrada ....
.... može se staviti preko bilo kog operatora na steku (kao i na prazan stek inače):
Operand b ....
.... direktno se prosleđuje u red:
Operator sabiranja ....
.... može se smestiti na stek (preko otvorene zagrade):
Operand c ....
.... direktno se prosleđuje u red:
Operator oduzimanja ....
.... ne može se smestiti na vrh steka, jer na vrhu steka stoji operator istog prioriteta:
Prvo je potrebno prebaciti operator sabiranja u red za čekanje ....
.... i tek potom se operator oduzimanja može smestiti na vrh steka:
Operand d ....
.... biće (po običaju), direktno prosleđen u red:
Zatvorena zagrada ....
.... pokrenuće pražnjenje steka do prve prethodno ubačene otvorene zagrade ....
.... što praktično znači da će operator oduzimanja (kao jedini operator 'između dve zagrade'), biti prosleđen u red za čekanje ....
.... posle čega će otvorena zagrada ....
.... biti obrisana sa vrha steka ....
.... a zatvorena zagrada (koja je pokrenula (delimično) pražnjenje steka) ....
.... jednostavno se zanemaruje:
Na kraju, pošto su tokeni istrošeni - a stek nije prazan - sadržaj steka (vidimo da je praktično u pitanju samo jedan operator) ....
.... biće prebačen u red ....
.... posle čega je izraz rešen.
Implementacija metode za prebacivanje izraza iz infiksne notacije u postfiksnu notaciju
U implementaciji metode za prebacivanje izraza iz infiksne notacije u postfiksnu notaciju, smatraćemo (zarad preglednosti i jednostavnosti), da svaki pojedinačni karakter iz ulazne niske predstavlja token, i takođe ćemo podrazumevati da je izraz pravilno zapisan (pri čemu su razmaci u izrazu dozvoljeni).
private void dodavanjePlusMinus(char c, Stack<char> stek, Queue<char> red)
{
if (stek.Peek() == '(' || stek.Peek() == '?') {
stek.Push(c);
}
else {
while (stek.Peek() == '+' || stek.Peek() == '-' ||
stek.Peek() == '*' || stek.Peek() == '/')
{
red.Enqueue(stek.Pop());
}
stek.Push(c);
}
}
private void dodavanjePutaKroz(char c, Stack<char> stek, Queue<char> red)
{
if (stek.Peek() == '(' || stek.Peek() == '?' ||
stek.Peek() == '+' || stek.Peek() == '-')
{
stek.Push(c);
}
else {
while (stek.Peek() == '/' || stek.Peek() == '*') {
red.Enqueue(stek.Pop());
}
stek.Push(c);
}
}
private void dodavanjeZatvorenaZagrada(char c, Stack<char> stek, Queue<char> red)
{
while (stek.Peek() != '(') {
red.Enqueue(stek.Pop());
}
stek.Pop();
}
private string Parse(string s)
{
Int32 i, d = s.Length;
String str = "";
Queue<char> red = new Queue<char>();
Stack<char> stek = new Stack<char>();
stek.Push('?');
for (i = 0; i < d; i++) {
char c = s[i];
if (c >= 97 && c <= 122) {
red.Enqueue(c);
}
else {
switch (c) {
case '(': stek.Push(c); break;
case '+':
case '-': dodavanjePlusMinus(c, stek, red); break;
case '*':
case '/': dodavanjePutaKroz(c, stek, red); break;
case ')': dodavanjeZatvorenaZagrada(c, stek, red); break;
default: break;
}
}
}
while (stek.Peek() != '?') red.Enqueue(stek.Pop());
ProcenaVrednosti(red);
while (red.Count > 0) str += red.Dequeue().ToString();
return str;
}
Kao što vidimo, u pitanju je jednostavna petlja koja redom prolazi kroz tokene i rešava svaki token "u mestu":
- preko
switchgrananja, znak (odnosno token) koji je dospeo na obradu, uparuje se sa jednom od kategorija tokena koje se prepoznaju - u zavisnosti od sadržaja tokena, poziva se jedna od radnih metoda za rešavanje pojedinačnih kategorija tokena (pri čemu su takve metode, kao što smo već videli, gotovo direktna implementacija pravila koja su navedena na početku)
Dalji koraci ....
Prebacivanje izraza iz infiksne notacije u postfiksnu notaciju, prvi je korak u računanju vrednosti izraza.
U sledećem članku koji je posvećen implementaciji algoritma Shunting Yard, predstavićemo deo algoritma koji je zadužen za računanje vrednosti izraza (i prikazaćemo implementaciju).