„Shunting-yard algoritmus” változatai közötti eltérés
| [nem ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Nincs szerkesztési összefoglaló |
|||
| (36 közbenső módosítás, amit 4 másik szerkesztő végzett, nincs mutatva) | |||
1. sor:
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
Az eljárás [[Verem (adatszerkezet)|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á.<ref>{{cite web
|access-date=2020-12-28
|title=Parsing Expressions by Recursive Descent
|url=http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
|website=www.engr.mun.ca
|author=Theodore Norvell
|date=1999
}}</ref> Az eljárást Djikstra a [[Mathematisch Centrum]] beszámolójában írta le először.<ref>{{cite web
|url=https://repository.cwi.nl/noauth/search/fullrecord.php?publnr=9251
|title=MR 34/61
}}{{Halott link|url=https://repository.cwi.nl/noauth/search/fullrecord.php?publnr=9251 |date=2021-08 }}</ref>
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 <code>1 + 2</code> átalakítás utáni alakja <code>1 2 +</code>. A jelölés fő erőssége a műveleti precedencia és a zárójelezés elhagyása. Például a <code>3 + 2 • 1</code> átalakítva <code>3 2 1 • +</code> lesz, a <code>(3+2)•1</code> pedig <code>3 2 + 1 •</code>, viszont a <code>3•(2+1)</code> alakja <code>3 2 1 + •</code> 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 ==
[[Fájl:Shunting yard.svg|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 <math>O(n)</math>, 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 ====
<syntaxhighlight lang=java line="1">
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;
}
}
</syntaxhighlight>
== 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 <code>3+4•2-5:1</code> műveletsort!
{| class="wikitable"
|+ 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 <code>3 4 2 • + 5 1 : -</code>.
=== Zárójelekkel ===
Alakítsuk át a <code>25 + 4• (5 + 2 • 3)-45 : 3 ^ 2</code> műveletsort!
{| class="wikitable"
|+ 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 <code>25 4 5 2 3 • + • 45 3 2 ^ : - +</code>
=== Függvények esete ===
Alakítsuk át a <code>3 • sin( π / 3 ) + 5 • cos( 3 • π / 2 )</code> kifejezést inverz lengyel jelölésűre!
{| class="wikitable"
|+ 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 <code>3 π 3 / sin • 5 3 π 2 / • cos • +</code>.
== Források ==
{{reflist}}
== Fordítás ==
{{fordítás|en|shunting-yard algorithm|oldid=1002380861}}
| |||