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 Djikstra-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á.
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 •.
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
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 kimentre íródik.
- A műveleti vermet az eljárás végén a kimenetre ürítjük.
Szemlélteté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
Pszeudokód
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 kimeentre */
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
Alább néhány megvalósítást láthatunk különböző programozási nyelveken.
Java programozási nyelv
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;
}
}
Python programozási nyelv
class Parser:
def Parser(self, input):
Fordítás
Ez a szócikk részben vagy egészben a shunting-yard algorithm című angol Wikipédia-szócikk 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.