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á. Az eljárást Djikstra a Mathematisch Centrum beszámolójában írta le először.
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 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 bélyegkép|Az algoritmus szemléltetése egy háromirányú vasúti kereszteződéssel
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 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 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;
Példák Lássuk néhány példát az algoritmus működésére! Egyszerű műveletsor Alakítsuk át a 3+4•2-5:1 műveletsort! + Az átalakítás lépései 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
Alakítsuk át a 25 + 4• (5 + 2 • 3)-45 : 3 ^ 2 műveletsort! + Az átalakítás lépései 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
Alakítsuk át a 3 • sin( π / 3 ) + 5 • cos( 3 • π / 2 ) kifejezést inverz lengyel jelölésűre!
+ Az átalakítás lépései 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 • +.
Jegyzetek
Fordítás
Kategória:Algoritmusok