Algoritmus posunovacího nádraží - Shunting-yard algorithm

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale její zdroje zůstávají nejasné, protože jí chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (srpen 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v počítačová věda, algoritmus posunovacího nádraží je metoda pro analýzu matematických výrazů uvedených v infixová notace. Může vytvořit buď postfixový notační řetězec, známý také jako Reverzní polská notace (RPN) nebo abstraktní syntaxový strom (AST). The algoritmus byl vynalezen Edsger Dijkstra a pojmenoval algoritmus „posunovacího dvora“, protože jeho operace se podobá a železniční posunovací dvůr. Dijkstra poprvé popsal Algoritmus posunovacího dvora v Mathematisch Centrum zpráva MR 34/61.

Stejně jako vyhodnocení RPN je algoritmus posunovacího dvora zásobník -na základě. Výrazy Infix jsou například formou matematické notace, na kterou je většina lidí zvyklá "3 + 4" nebo "3 + 4 × (2 − 1)". Pro převod existují dva texty proměnné (struny ), vstup a výstup. Je tam také zásobník který obsahuje operátory, které ještě nebyly přidány do výstupní fronty. Chcete-li převést, program načte každý symbol v pořadí a na základě tohoto symbolu udělá něco. Výsledkem výše uvedených příkladů bude (v Reverzní polská notace ) "3 4 +" a "3 4 2 1 − × +", resp.

Algoritmus posunovacího nádraží byl později zobecněn na analýza priority operátora.

Jednoduchý převod

1. Vstup: 3 + 4
2. Stiskněte 3 na výstup fronta (kdykoli je číslo načteno, je odesláno na výstup)
3. Tlačit + (nebo jeho ID) na operátora zásobník
4. Zatlačte 4 do výstupní fronty
5. Po přečtení výrazu pop operátory mimo zásobník a přidat je do výstupu.

   V tomto případě existuje pouze jeden znak „+“.

6. Výstup: 3 4 +

To již ukazuje několik pravidel:

• Všechna čísla jsou načtena na výstup.
• Na konci čtení výrazu vysuňte všechny operátory ze zásobníku a na výstup.

Grafické znázornění

Grafické znázornění algoritmu pomocí a třícestný železniční uzel. Vstup je zpracováván po jednom symbolu: pokud je nalezena proměnná nebo číslo, zkopíruje se přímo na výstup a), c), e), h). Pokud je symbol operátor, je vložen do sady operátorů b), d), f). Pokud je priorita operátora nižší než priorita operátorů v horní části zásobníku nebo jsou precedenty stejné a operátor je ponechán asociativní, pak je tento operátor vysunut ze zásobníku a přidán k výstupu g). Nakonec jsou všechny zbývající operátory vyskakovány ze zásobníku a přidány k výstupu i).

Algoritmus podrobně

Důležité pojmy: Žeton, Funkce, Asociativita operátora, Přednost

/ * Tato implementace neimplementuje složené funkce, funkce s proměnným počtem argumentů a unární operátory. * /zatímco existují tokeny ke čtení: přečtěte si token. -li token je číslo, pak: posuňte jej do výstupní fronty. jinak pokud token je funkce pak: zatlačte na zásobník operátora jinak pokud token je operátor pak:        zatímco ((v horní části zásobníku operátorů je operátor) a ((operátor v horní části zásobníku operátorů má větší přednost) nebo (operátor v horní části zásobníku operátorů má stejnou přednost a token je ponechán asociativní)) a (operátor v horní části zásobníku operátorů není levá závorka)): vyskakují operátory ze zásobníku operátorů do výstupní fronty. zatlačte jej na zásobník operátora. jinak pokud token je levá závorka (tj. „(“), pak: zatlačte na zásobník operátora. jinak pokud token je pravá závorka (tj. „)“), pak:        zatímco operátor v horní části zásobníku operátorů není levá závorka: vysuňte operátor ze zásobníku operátorů do výstupní fronty. / * Pokud se zásobník vyčerpá bez nalezení levé závorky, pak jsou v závorkách neodpovídající. * /        -li v horní části zásobníku operátorů je levá závorka, pak: vysuňte operátor ze zásobníku operátorů a zahoďte ho -li v horní části zásobníku operátorů je funkční token, pak: vyskočí funkci ze zásobníku operátorů do výstupní fronty./ * After while loop, if operator stack not null, pop everything to output queue * /-li neexistují žádné další žetony ke čtení pak:    zatímco v zásobníku jsou stále tokeny operátorů: / * Pokud je token operátora v horní části zásobníku v závorkách, pak jsou v závorkách neodpovídající. * /        vysuňte operátor ze zásobníku operátorů do výstupní fronty. konec.

Abychom mohli analyzovat složitost běhu tohoto algoritmu, je třeba si jen uvědomit, že každý token bude přečten jednou, každé číslo, funkce nebo operátor budou vytištěny jednou a každá funkce, operátor nebo závorka budou vloženy do zásobníku a vyskočil ze zásobníku jednou - proto je na token proveden maximálně konstantní počet operací a doba běhu je tedy O (n) —Lineární ve velikosti vstupu.

Algoritmus posunovacího dvora lze také použít k vytvoření prefixové notace (známé také jako Polská notace ). Chcete-li to udělat, jednoduše byste začali od konce řetězce tokenů, které se mají analyzovat, a pracovat zpět, obráťte výstupní frontu (proto se z výstupní fronty stane výstupní zásobník) a otočte chování levé a pravé závorky (nezapomeňte, že nyní -levé chování v závorkách by se mělo objevit, dokud nenajde nyní pravou závorku). A změna podmínky asociativity doprava.

Podrobný příklad

Vstup: 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3

Operátor	Přednost	Asociativita
^	4	Že jo
×	3	Vlevo, odjet
÷	3	Vlevo, odjet
+	2	Vlevo, odjet
−	2	Vlevo, odjet

Symbol ^ představuje energetický operátor.

Žeton	Akce	Výstup (v RPN )	Operátor zásobník	Poznámky
3	Přidejte token k výstupu	3
+	Push token to stack	3	+
4	Přidejte token na výstup	3 4	+
×	Push token to stack	3 4	× +	× má vyšší prioritu než +
2	Přidejte token na výstup	3 4 2	× +
÷	Pop stack na výstup	3 4 2 ×	+	÷ a × mají stejnou přednost
	Push token to stack	3 4 2 ×	÷ +	÷ má vyšší prioritu než +
(	Push token to stack	3 4 2 ×	( ÷ +
1	Přidejte token na výstup	3 4 2 × 1	( ÷ +
−	Push token to stack	3 4 2 × 1	− ( ÷ +
5	Přidejte token na výstup	3 4 2 × 1 5	− ( ÷ +
)	Pop stack na výstup	3 4 2 × 1 5 −	( ÷ +	Opakováno, dokud nebyl nalezen znak „(“
	Pop stack	3 4 2 × 1 5 −	÷ +	Zrušte odpovídající závorky
^	Push token to stack	3 4 2 × 1 5 −	^ ÷ +	^ má vyšší prioritu než ÷
2	Přidejte token na výstup	3 4 2 × 1 5 − 2	^ ÷ +
^	Push token to stack	3 4 2 × 1 5 − 2	^ ^ ÷ +	^ je vyhodnocován zprava doleva
3	Přidejte token na výstup	3 4 2 × 1 5 − 2 3	^ ^ ÷ +
konec	Vysuňte celý zásobník na výstup	3 4 2 × 1 5 − 2 3 ^ ^ ÷ +

Vstup: hřích (max (2, 3) ÷ 3 × π )

Žeton	Akce	Výstup = (v RPN )	Operátor zásobník	Poznámky
hřích	Push token to stack		hřích
(	Push token to stack		(hřích
max	Push token to stack		max (hřích
(	Push token to stack		(max. (hřích
2	Přidejte token na výstup	2	(max. (hřích
,	ignorovat	2	(max. (hřích
3	Přidejte token k výstupu	2 3	(max. (hřích
)	pop stack na výstup	2 3	(max. (hřích	Opakováno, dokud „(“ není v horní části zásobníku
Pop stack	2 3	max (hřích	Zahodit odpovídající závorky
÷	Pop stack na výstup	2 3 max	(hřích
	Push token to stack	2 3 max	÷ (hřích
3	Přidejte token k výstupu	2 3 max 3	÷ (hřích
×	Pop stack na výstup	2 3 max. 3 ÷	(hřích
	Push token to stack	2 3 max. 3 ÷	× (hřích
π	Přidejte token k výstupu	2 3 max. 3 ÷ π	× (hřích
)	Pop stack na výstup	2 3 max. 3 ÷ π ×	(hřích	Opakováno, dokud „(“ není v horní části stohu
	Pop stack	2 3 max. 3 ÷ π ×	hřích	Zahodit odpovídající závorky
konec	Vysuňte celý zásobník na výstup	2 3 max. 3 ÷ π × hřích

Viz také

• Analyzátor priority operátorů
• Stacková klasifikace

externí odkazy

• Dijkstrův původní popis algoritmu posunovacího dvora
• Implementace gramotných programů v jazyce C.
• Java applet demonstrující algoritmus posunovacího dvora
• Widget Silverlight demonstrující algoritmus posunovacího dvora a vyhodnocení aritmetických výrazů
• Analýza výrazů rekurzivním sestupem Theodore Norvell © 1999–2001. Datum přístupu 14. září 2006.
• Kód Matlabu, vyhodnocení aritmetických výrazů pomocí algoritmu posunovacího dvora