Shunting-yard algoritmus

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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 kimentre íródik.
  • A műveleti vermet az eljárás végén a kimenetre ürítjük.


Szemléltetés[szerkeszté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[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!

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ő verembe 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!

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[szerkesztés]

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 • +.

Források[szerkesztés]

  1. Theodore Norvell: Parsing Expressions by Recursive Descent. www.engr.mun.ca , 1999 (Hozzáférés: 2020. december 28.)
  2. 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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.