Algoritmus seřaďovacího nádraží
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od
verze recenzované 3. června 2021; kontroly vyžadují
2 úpravy .
Algoritmus seřaďovacího nádraží je způsob analýzy matematických a/nebo logických výrazů reprezentovaných infixovou notací . Lze jej použít k vytvoření reverzní polské notace nebo výstupu abstraktního stromu syntaxe . Algoritmus navrhl Edsger Dijkstra a pojmenoval jej „algoritmus seřaďovacího nádraží“, protože se podobá provozu železničního seřaďovacího nádraží .
Stejně jako při výpočtu hodnot výrazů v obráceném polském zápisu funguje algoritmus pomocí zásobníku . Nejčastěji lidé používají infixový zápis matematických výrazů, jeho příklady jsou 2+4 a 3+6*(3-2). Pro převod do reverzní polské notace se používají 2 řetězce: vstup a výstup a zásobník pro ukládání příkazů, které ještě nebyly přidány do výstupní fronty. Při převodu algoritmus čte 1 znak a provádí akce v závislosti na tomto znaku.
Algoritmus
- Dokud nebudou zpracovány všechny tokeny:
- Přečíst token .
- Pokud je token číslo , přidejte jej do výstupní fronty.
- Pokud je token funkcí , zatlačte jej na hromádku.
- Pokud je token oddělovačem argumentů funkce (například čárka):
- Dokud žeton v horní části balíčku není otevřená závorka:
- Odeslat příkaz ze zásobníku do výstupní fronty.
- Pokud zásobník skončí dříve, než se objeví token otevírací složené závorky , pak se oddělovač argumentů funkce (čárka) vynechá z výrazu nebo se vynechá otevírací složená závorka .
- Pokud je token operátor op1 , pak:
- Dokud je v horní části zásobníku tokenový operátor op2, jehož priorita je větší nebo rovna prioritě op1 a pokud jsou priority stejné, op1 je vlevo asociativní :
- Push op2 ze zásobníku do výstupní fronty;
- Zatlačte op1 na zásobník.
- Pokud je žeton otevřená závorka , zatlačte jej na hromádku.
- Pokud je token uzavírací složená závorka :
- Pokud žeton na vrcholu zásobníku není otevřená závorka
- Odeslat příkaz ze zásobníku do výstupní fronty.
- Pokud zásobník skončí dříve, než je nalezen token úvodní závorky , pak závorka ve výrazu chybí.
- Otevřete otevřenou závorku ze zásobníku, ale nepřidávejte ji do výstupní fronty.
- Pokud je token v horní části zásobníku funkcí, posuňte jej do výstupní fronty.
- Pokud na vstupu nezbývají žádné další tokeny:
- Dokud jsou v zásobníku žetony operátorů:
- Pokud je token operátoru v horní části zásobníku otevřená závorka , pak závorka ve výrazu chybí.
- Odeslat příkaz ze zásobníku do výstupní fronty.
Každé číslo tokenu, funkce nebo operátor se vytiskne pouze jednou a každá funkce tokenu, operátor nebo závorka bude přidána a odebrána ze zásobníku jednou. Konstantní počet operací na token, lineární složitost algoritmu O( n ).
Odkazy