Shunting-yard algoritmus
A Shunting-yard algoritmus egy eljárás az infix jelöléssel megadott műveletsorok számítógép által könnyebben kezelhető fordított lengyel jelölésűvé alakítására. A név eredete a kifejlesztő Edsger Dijkstrához köthető, aki szerint az algoritmus a rendező pályaudvarra (angolul shunting yard) emlékeztette.
Az eljárás verem alapú, így nem csak lengyel jelölésűvé alakító eszközt láthatunk benne, de akár kódokat is alakíthatunk absztrakt szintakszisfává.[1] Az eljárást Djikstra a Mathematisch Centrum beszámolójában írta le először.[2]
Az eljárás során a bemenő adatsorból egy kimenő adatsort állítunk elő, valamint a fel nem használt szimbólumok tárolására igénybe veszünk egy vermet. Például a hagyományos (infix) módon leírt 1 + 2 átalakítás utáni alakja 1 2 +. A jelölés fő erőssége a műveleti precedencia és a zárójelezés elhagyása. Például a 3 + 2 • 1 átalakítva 3 2 1 • + lesz, a (3+2)•1 pedig 3 2 + 1 •, viszont a 3•(2+1) alakja 3 2 1 + • formában lesz olvasható.
Az algoritmus minden helyes kifejezést képes feldolgozni, de nem dob el minden helytelent. A hibás zárójelezést viszont például minden esetben észreveszi.
Az algoritmus általános formája a műveletisorrend-kifejtés.
Egy egyszerű példa
[szerkesztés]Be: 3+4 A 3 kimenetre kerül A + a műveleti verembe kerül A 4 a kimenetre kerül A műveleti vermet a kimenetre írjuk
Két lényeges szabály a fenti példából máris kiderül:
- Minden szám azonnal a kimenetre íródik.
- A műveleti vermet az eljárás végén a kimenetre ürítjük.
Szemléltetés
[szerkesztés]
Az eljárást a képen látható háromirányú vasúti kereszteződés szemlélteti a legjobban. Ahogy érkezik a kifejezés, mint egy vonat, minden számot (szimbólumot) továbbküldünk, a műveleteket pedig a verembe (oldalvágányra) tereljük. Ha az érkező művelet alacsonyabb rendű, mint a verem tetején lévő művelet, akkor a veremből kivesszük a műveletet, és a szerelvény végére írjuk. Ugyanez a helyzet a balasszociatív műveletekkel is.
Az algoritmus
[szerkesztés]Pszeudokód
[szerkesztés]Amíg van token a bemeneten:
Olvasd be a tokent
Ha a token szám, Akkor:
Tedd a tokent a kimenetre
Egyébként Ha a token függvény, Akkor:
Tedd a tokent a műveleti verembe
Egyébként Ha a token művelet, Akkor:
Amíg van művelet a veremben, és (az a művelet magasabb rendű vagy (azonos rendű és balasszociatív)) és nem baloldali zárójel:
Tedd a veremből a műveletet a kimenetre
Tedd a műveletet a verembe
Egyébként Ha a token baloldali zárójel, Akkor:
Tedd a tokent a verembe
Egyébként Ha a token jobb oldali zárójel, Akkor:
Amíg a verem tetején nem baloldali zárójel van:
Tedd a legfelső műveletet a kimenetre
/* Ha nincs baloldali zárójel, akkor a bemenet hibás */
Ha a verem tetején baloldali zárójel van, Akkor:
Vedd ki a zárójelet és dobd el
Ha a token függvény, Akkor:
Tedd a tokent a kimenetre
/* Ha elfogyott a bemenet, akkor tegyük a vermet a kimenetre */
Ha nincs több beolvasható token, Akkor:
Amíg van a verem tetején token:
Tedd a verem tetejét a kimenetre
Vége
Ha megvizsgáljuk az algoritmus összetettségét, azt találjuk, hogy minden tokent egyszer olvasunk be, mindegyiket egyszer írjuk ki, valamint a függvények, az operátorok és a zárójelek egyszer kerülnek a verembe és egyszer kerülnek ki belőle. Egy tokenre ez alapján meghatározott, állandó számú művelet jut, így a műveletigény , azaz a végrehajtás ideje a tokenek számával egyenesen arányos.
Az eljárás egyszerűen átalakítható lengyel jelölésűvé, ehhez mindössze a tokenek listáját a végéről kezdve kell feldolgozni, majd a kapott kimenetet megfordítani. Változás csak az asszociativitás és a zárójelek esetén van, a bal és jobb felcserélése után.
Megvalósítások
[szerkesztés]Alább néhány megvalósítást láthatunk különböző programozási nyelveken.
Java programozási nyelv
[szerkesztés]import java.util.Stack;
import java.util.StringTokenizer;
public class Parser{
StringTokenizer st;
public Parser(String input){
st = new StringTokenizer(input, Operator.getOperatorString()+"()", true);
}
public String[] convertToRPN(){
Stack<String> opStack = new Stack<String>();
String[] rpn = new String[st.countTokens()];
boolean wasOperator = true;
int index = 0;
while( st.hasMoreTokens() ){
String temporary = st.nextToken();
if( temporary.equals("(")){
opStack.push(temporary);
wasOperator = true;
} else if( (temporary.equals("-") ) && (wasOperator)){
rpn[index] = Double.toString( -1 * Double.parseDouble(st.nextToken()) );
index++;
} else if( temporary.equals(")")){
while( !(opStack.peek().equals("(")) ){
rpn[index] = opStack.pop();
index++;
wasOperator = false;
}
opStack.pop();
}else if( Operator.isOperator(temporary) ){
while( ( !(opStack.empty()) ) && ( !(opStack.peek().equals("(")) ) && (Operator.getPrecedence(opStack.peek()).byteValue() > Operator.getPrecedence(temporary).byteValue() ) ){
rpn[index] = opStack.pop();
index++;
}
opStack.push(temporary);
wasOperator = true;
} else {
rpn[index] = temporary;
index++;
wasOperator = false;
}
}
while( !(opStack.empty()) ){
rpn[index] = opStack.pop();
index++;
}
return rpn;
}
}
Példák
[szerkesztés]Lássuk néhány példát az algoritmus működésére!
Egyszerű műveletsor
[szerkesztés]Alakítsuk át a 3+4•2-5:1 műveletsort!
| Token | Utasítás | Kimenő sor | Műveleti verem | Megjegyzések |
|---|---|---|---|---|
| 3 | Tedd a tokent a kimenő sorba | 3 | ||
| + | Tedd a tokent a műveleti verembe | 3 | + | |
| 4 | Tedd a tokent a kimenő sorba | 3 4 | + | |
| • | Tedd a tokent a műveleti verembe | 3 4 | • + | |
| 2 | Tedd a tokent a kimenő sorba | 3 4 2 | • + | |
| - | Írd a műveleti vermet a kimenő sorba, majd tedd a tokent a műveleti verembe | 3 4 2 • + | - | A kivonás precedenciája alacsonyabb, mint a szorzásé |
| 5 | Tedd a tokent a kimenő sorba | 3 4 2 • + 5 | - | |
| : | Tedd a tokent a műveleti verembe | 3 4 2 • + 5 | : - | |
| 1 | Tedd a tokent a kimenő sorba | 3 4 2 • + 5 1 | : - | |
| Írd ki a műveleti vermet a kimenő sorba | 3 4 2 • + 5 1 : - | Vége az eljárásnak |
Az átalakított forma tehát 3 4 2 • + 5 1 : -.
Zárójelekkel
[szerkesztés]Alakítsuk át a 25 + 4• (5 + 2 • 3)-45 : 3 ^ 2 műveletsort!
| Token | Utasítás | Kimenő sor | Műveleti verem | Megjegyzések |
|---|---|---|---|---|
| 25 | Tedd a tokent a kimenő sorba | 25 | ||
| + | Tedd a tokent a műveleti verembe | 25 | + | |
| 4 | Tedd a tokent a kimenő sorba | 25 4 | + | |
| • | Tedd a tokent a műveleti verembe | 25 4 | • + | |
| ( | Tedd a tokent a műveleti verembe | 25 4 | ( • + | Bal zárójel |
| 5 | Tedd a tokent a kimenő sorba | 25 4 5 | ( • + | |
| + | Tedd a tokent a műveleti verembe | 25 4 5 | + ( • + | |
| 2 | Tedd a tokent a kimenő sorba | 25 4 5 2 | + ( • + | |
| • | Tedd a tokent a műveleti verembe | 25 4 5 2 | • + ( • + | |
| 3 | Tedd a tokent a kimenő sorba | 25 4 5 2 3 | • + ( • + | |
| ) | Írd ki a műveleti vermet az első bal zárójelig, a zárójelet dobd el | 25 4 5 2 3 • + | • + | Ez volt a lezáró jel |
| - | Vedd ki a legfelső műveletet a veremből, majd tedd a tokent a műveleti verembe | 25 4 5 2 3 • + • | - + | |
| 45 | Tedd a tokent a kimenő sorba | 25 4 5 2 3 • + •45 | - + | |
| : | Tedd a tokent a műveleti verembe | 25 4 5 2 3 • + • 45 | : - + | |
| 3 | Tedd a tokent a kimenő sorba | 25 4 5 2 3 • + • 45 3 | : - + | |
| ^ | Tedd a tokent a műveleti verembe | 25 4 5 2 3 • + • 45 3 | ^ : - + | |
| 2 | Tedd a tokent a kimenő sorba | 25 4 5 2 3 • + • 45 3 2 | ^ : - + | Ez az utolsó token! |
| Írd ki a műveleti vermet a kimenő sorba | 25 4 5 2 3 • + • 45 3 2 ^ : - + | Vége |
A kifejezés postfix alakja tehát 25 4 5 2 3 • + • 45 3 2 ^ : - +
Függvények esete
[szerkesztés]Alakítsuk át a 3 • sin( π / 3 ) + 5 • cos( 3 • π / 2 ) kifejezést inverz lengyel jelölésűre!
| Token | Utasítás | Kimenő sor | Műveleti verem | Megjegyzések |
|---|---|---|---|---|
| 3 | Tedd a tokent a kimenő sorba | 3 | ||
| • | Tedd a tokent a műveleti verembe | 3 | • | |
| sin | Tedd a tokent a műveleti verembe | 3 | sin • | A függvények is műveletnek számítanak |
| ( | Tedd a tokent a műveleti verembe | 3 | ( sin • | Baloldali zárójel |
| π | Tedd a tokent a kimenő sorba | 3 π | ( sin • | |
| / | Tedd a tokent a műveleti verembe | 3 π | / ( sin • | |
| 3 | Tedd a tokent a kimenő sorba | 3 π 3 | / ( sin • | |
| ) | Írd ki a baloldali zárójelig a műveleti vermet a kimenő sorba | 3 π 3 / | sin • | A zárójeleket párban eldobjuk |
| + | Írd ki a magasabb precedenciájú műveleteket a veremből, majd tedd a tokent a műveleti verembe | 3 π 3 / sin • | + | |
| 5 | Tedd a tokent a kimenő sorba | 3 π 3 / sin • 5 | + | |
| • | Tedd a tokent a műveleti verembe | 3 π 3 / sin • 5 | • + | |
| cos | Tedd a tokent a műveleti verembe | 3 π 3 / sin • 5 | cos • + | A függvények műveletnek számítanak |
| ( | Tedd a tokent a műveleti verembe | 3 π 3 / sin • 5 | ( cos • + | Baloldali zárójel |
| 3 | Tedd a tokent a kimenő sorba | 3 π 3 / sin • 5 3 | ( cos • + | |
| • | Tedd a tokent a műveleti verembe | 3 π 3 / sin • 5 3 | • ( cos • + | |
| π | Tedd a tokent a kimenő sorba | 3 π 3 / sin • 5 3 π | • ( cos • + | |
| / | Tedd a tokent a műveleti verembe | 3 π 3 / sin • 5 3 π | / • ( cos • + | |
| 2 | Tedd a tokent a kimenő sorba | 3 π 3 / sin • 5 3 π 2 | / • ( cos • + | |
| ) | Írd ki a baloldali zárójelig a műveleti vermet a kimenő sorba | 3 π 3 / sin • 5 3 π 2 / • | cos • + | A zárójeleket párban eldobjuk |
| Nincs több token, írd ki a műveleti vermet a kimenő sorba | 3 π 3 / sin • 5 3 π 2 / • cos • + | Vége az eljárásnak |
A kifejezés inverz lengyel alakja tehát 3 π 3 / sin • 5 3 π 2 / • cos • +.
Források
[szerkesztés]- ↑ Theodore Norvell: Parsing Expressions by Recursive Descent. www.engr.mun.ca , 1999 (Hozzáférés: 2020. december 28.)
- ↑ MR 34/61[halott link]
Fordítás
[szerkesztés]Ez a szócikk részben vagy egészben a shunting-yard algorithm című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.