Algoritmus shunting-yard

Shunting yard algoritmus je metoda pro syntaktickou analýzu matematických výrazů zapsaných v infixové notaci. Algoritmus může být použit k převodu výrazů do reverzní polské notace (RPN), nebo do abstraktního syntaktického stromu (AST).

Algoritmus byl vyvinut Edsgerem Dijkstrou a pojmenován Shunting yard (česky seřaďovací nádraží), protože jeho princip se podobá seřaďovacímu nádraží.

Podobně jako interpret reverzní polské notace je shunting yard založený na používání zásobníku. Infixovou formu zápisu používá většina lidí (například 3+4 nebo 3+4*(2−1)). Ke konverzi do RPN je zapotřebí dvou textových proměnných (jednu pro vstup a druhou pro výstup) a jednoho zásobníku pro uchovávání operátorů které zatím nebyly vloženy do výstupu.

Ukázka jednoduché konverze

Vstup: 3+4

Přidej 3 do výstupní fronty (pokaždé když přečte číslo, přidá ho do výstupu)
Přidej + (nebo jeho ID) do zásobníku operátorů
Vlož 4 do výstupu
Po přečtení celého vzorce vyjmi operátory ze zásobníku a vlož je do výstupní fronty
V tomto případě je zde pouze jedno, "+"

Výstup: 3 4 +

Z této ukázky je možno vypozorovat několik pravidel:

Všechna čísla jsou okamžitě po přečtení přidána do výstupu.
Po přečtení vzorce je nutné ze zásobníku vyjmout všechny operátory a vložit je do výstupní fronty.

Detailní popis algoritmu

Dokud jsou zde tokeny ke čtení:
- Přečti token.
- Pokud je token číslo, přidej ho do výstupní fronty.
- Pokud je token funkce, vlož ho na zásobník.
- Pokud je token oddělovač argumentů funkce (nejčastěji čárka):
  - Dokud nebude na vrcholu zásobníku levá závorka, vybírej z něj operátory a vkládej je do výstupu. Jestliže se zásobník vyprázdní a závorka nebude nalezena, oddělovač byl buď na nesprávném místě, nebo ve vstupu chybí otevírací závorka.
- Pokud je token operátor (dále jen o₁), tak:
  - dokud bude na vrcholu zásobníku operátor (s výjimkou závorek), o₂, tak:
    - pokud je o₁ asociativní zleva a jeho priorita je menší nebo stejná (≤) jako priorita o₂, nebo o₁ je asociativní zprava a jeho priorita je nižší (<) než priorita operátoru o₂, vyjmi operátor o₂ ze zásobníku a vlož ho do výstupní fronty, jinak ukonči cyklus.
  - vlož operátor o₁ na zásobník.
- Pokud je token levá závorka, vlož ho na zásobník.
- Pokud je token pravá závorka:
  - Dokud na vrcholu zásobníku nebude levá závorka, vybírej operátory ze zásobníku a zapisuj je do výstupní fronty.
  - Vyjmi ze zásobníku levou závorku, ale nevkládej jí do výstupní fronty.
  - Pokud je na vrcholu zásobníku token identifikovaný jako funkce, vlož ho do výstupu.
  - Pokud je zásobník prázdný a nepodařilo se najít levou závorku, jedná se o neuzavřený výraz a je vhodné oznámit chybu.
Jestliže byly zpracovány všechny tokeny ze vstupu:
- Dokud budou v zásobníku operátory:
  - Jestliže operátor na vrcholu zásobníku je závorka, ve výrazu jsou neuzavřené závorky a je vhodné ohlásit chybu.
  - Vyjmi operátor ze zásobníku a vlož ho do výstupní fronty.
Konec.

Časová náročnost tohoto algoritmu je lineární v závislosti na velikosti programu, protože každý token je načten pouze jednou, každá funkce a každý operátor je na zásobník vložený a vyjmutý pouze jednou a každý prvek je vložen do výstupu pouze jednou.

Detailní ukázka

Vstup: 3 + 4 * 2 / ( 1 – 5 ) ^ 2 ^ 3
Token	Akce	Výstup (v RPN)	Zásobník operátorů	Poznámky
3	Přidej token do výstupu	3
+	Přidej token na zásobník	3	+
4	Přidej token do výstupu	3 4	+
*	Přidej token na zásobník	3 4	+ *	* má větší prioritu než +
2	Přidej token do výstupu	3 4 2	+ *
/	Vyjmi ze zásobníku a vypiš	3 4 2 *	+	/ a * mají stejnou prioritu
/	Přidej token na zásobník	3 4 2 *	+ /	/ má větší prioritu než +
(	Přidej token na zásobník	3 4 2 *	+ / (
1	Přidej token do výstupu	3 4 2 * 1	+ / (
-	Přidej token na zásobník	3 4 2 * 1	+ / ( -
5	Přidej token do výstupu	3 4 2 * 1 5	+ / ( -
)	Vyjmi ze zásobníku a vypiš	3 4 2 * 1 5 −	+ / (	Opakuj dokud nenajdeš "("
)	Vyjmi ze zásobníku	3 4 2 * 1 5 −	+ /	Zahoď nalezenou závorku
^	Přidej token na zásobník	3 4 2 * 1 5 −	+ / ^	^ má větší prioritu než /
2	Přidej token do výstupu	3 4 2 * 1 5 − 2	+ / ^
^	Přidej token na zásobník	3 4 2 * 1 5 − 2	+ / ^ ^	^ je vyhodnoceno zprava doleva
3	Přidej token do výstupu	3 4 2 * 1 5 − 2 3	+ / ^ ^
konec	Vypiš zbytek zásobníku	3 4 2 * 1 5 − 2 3 ^ ^ / +

Pokud píšete interpret, výstup můžete tokenizovat a zapsat do zkompilovaného souboru k pozdější interpretaci. Konverzí z infixové notace do RPN můžete také zjednodušit vyhodnocování matematických výrazů. To provedete tak, jako kdybyste vyhodnocovali RPN výraz, nicméně pokud narazíte na proměnnou, jejíž hodnota je nulová a vždy když operátor má nulovou hodnotu, tak jeho hodnotu a parametry vypište na výstup (tohle je zjednodušení – problémy nastanou, pokud jsou jako parametry operátory). Pokud operátor nemá nulový parametr, jeho hodnota může být vypsána na výstup. Tato metoda očividně neobsahuje všechna možná zjednodušení – je to většinou jako optimalizace pomocí constant folding.

Související články

Reference

V tomto článku byl použit překlad textu z článku Shunting-yard algorithm na anglické Wikipedii.

Externí odkazy

(anglicky) Java Applet demonstrující Shunting yard algoritmus (vyžaduje javu)
(anglicky) Infix to RPN Algorithm
(anglicky) Originální popis Shunting yard algoritmu
(anglicky) Ukázka zdrojového kódu v C Archivováno 8. 2. 2009 na Wayback Machine.