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

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

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 ${\displaystyle O(n)}$, 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 • +.