Shunting-yard-Algorithmus

Grafische Illustration des Algorithmus als 3-Weg-Weichenstellung

Der Shunting-yard-Algorithmus (deutsch: Rangierbahnhof-Algorithmus) ist eine Methode, um mathematische Terme von der Infixnotation in die umgekehrte polnische Notation oder in einen abstrakten Syntaxbaum zu überführen. Der Algorithmus wurde von Edsger W. Dijkstra erfunden und mit englisch shunting yard ‚Rangierbahnhof‘ benannt, weil er in seiner Arbeitsweise an einen Rangierbahnhof erinnert.

Funktionsweise

Der Shunting-yard-Algorithmus benötigt für die Konversion sowohl eine Input- als auch eine Outputqueue sowie einen Stack, der für das Zwischenspeichern der Operatoren benötigt wird. Der Inputstring wird zeichenweise gelesen, wobei alle Zahlen direkt und in derselben Reihenfolge in die Ausgabevariable geschrieben werden. Falls das anstehende Zeichen ein Operationszeichen ist, wird es auf den Operatorenstack gelegt. Falls bereits ein Operator auf dem Stack liegt, wird anhand der Operatorrangfolge und der Operatorassoziativität entschieden, ob der neue Operator direkt auf den Stack gelegt wird oder ob der Stack zuerst in den Output geleert wird.

Öffnende Klammern werden ebenfalls auf den Operatorstack gelegt, allerdings werden sie beim Entfernen nicht in den Outputstream geschrieben. Bei schließenden Klammern wird der Stack bis zum Antreffen einer öffnenden Klammer geleert; sollte keine öffnende Klammer gefunden werden, ist der Inputstring unvollständig, wobei allerdings die Fehlerbehandlung nicht durch den Algorithmus definiert wird.

Im Detail

Es folgt ein deutscher Pseudocode, der in die meisten Programmiersprachen einfach übersetzt und angepasst werden kann. 

Stack (mit LIFO-Prinzip) sowie Ausgabequeue (mit FIFO-Prinzip) anlegen.
SOLANGE Tokens verfügbar sind:
    Token einlesen.
    WENN Token IST-Zahl:
        Token ZU Ausgabe.
    ENDEWENN
    WENN Token IST-Funktion:
        Token ZU Stack.
    ENDEWENN
    WENN Token IST-Argumenttrennzeichen:
        BIS Stack-Spitze IST öffnende-Klammer:
            Stack-Spitze ZU Ausgabe.
            FEHLER-BEI Stack IST-LEER:
                GRUND (1) Ein falsch platziertes Argumenttrennzeichen.
                GRUND (2) Der schließenden Klammer geht keine öffnende voraus.
            ENDEFEHLER
        ENDEBIS
    ENDEWENN
    WENN Token IST-Operator
        SOLANGE Stack IST-NICHT-LEER UND
                Stack-Spitze IST Operator UND
                (Präzedenz von Token IST-KLEINER Präzedenz von Stack-Spitze ODER
                 Präzedenz von Token IST-GLEICH Präzedenz von Stack-Spitze UND
                 Token IST-linksassoziativ)
            Stack-Spitze ZU Ausgabe.
        ENDESOLANGE
        Token ZU Stack.
    ENDEWENN
    WENN Token IST öffnende-Klammer:
        Token ZU Stack.
    ENDEWENN
    WENN Token IST schließende-Klammer:
        BIS Stack-Spitze IST öffnende-Klammer:
            FEHLER-BEI Stack IST-LEER:
                GRUND (1) Der schließenden Klammer geht keine öffnende voraus.
            ENDEFEHLER
            Stack-Spitze ZU Ausgabe.
        ENDEBIS
        Stack-Spitze (öffnende-Klammer) entfernen
        WENN Stack-Spitze IST-Funktion:
            Stack-Spitze ZU Ausgabe.
        ENDEWENN
    ENDEWENN
ENDESOLANGE
BIS Stack IST-LEER:
    FEHLER-BEI Stack-Spitze IST öffnende-Klammer:
        GRUND (1) Es gibt mehr öffnende als schließende Klammern.
    ENDEFEHLER
    Stack-Spitze ZU Ausgabe.
ENDEBIS

Dieser Algorithmus setzt voraus, dass alle Tokens vom Parser richtig erkannt werden und gültig sind. Insbesondere die Überlagerung (Vorzeichen versus Operator) der Zeichen „+“ und „−“ übernimmt dieser Algorithmus nicht. Ein Konflikt von rechts- und linksassoziativen Operatoren mit gleicher Präzedenz wird nicht abgefangen.

Der „lesende“ Zugriff auf den Stack (z. B. bei „Stack-Spitze IST“) und der „nehmende“ (bei „Stack-Spitze ZU“) werden vorausgesetzt.

Vorausgesetzte Funktionen sind:

  • Erkennen von (vorzeichenbehafteten) Zahlen
  • Erkennen von Funktionen
  • Erkennen von Argumenttrennzeichen
  • Erkennen von Operatoren
  • Feststellen der Operatorassoziativität
  • Feststellen der Operatorpräzedenz (hier bedeutet höhere Präzedenz eine stärkere Bindung), die Präzedenz einer Funktion ist maximal

Beispiele

Die folgenden in Infixnotation gegebenen Rechnungen sollen umgeformt werden. Es wird dokumentiert, was geschieht.

Präzedenzen: (+,−) < (·,:) < (^) < Funktionen

(3 + 4)(5 − 6)

  1. Tokens zusammenfassen: (3+4)(5−6) (Hier: Jedes Zeichen ist ein Token)
  2. ( auf den Stack
  3. 3 zur Ausgabe
  4. + auf den Stack
  5. 4 zur Ausgabe
  6. ):
    1. + zur Ausgabe
    2. ( vom Stack entfernen
  7. Operator erwartet, aber ( gefunden:
    1. implizites · auf den Stack
    2. ( auf den Stack
  8. 5 zur Ausgabe
  9. − auf den Stack
  10. 6 zur Ausgabe
  11. ):
    1. − zur Ausgabe
    2. ( vom Stack entfernen
  12. Ende: · zur Ausgabe

Ausgabe:34+56−·

1 + 2 − 3 · 4 + 5^6^7 · 8 − 9

  1. Tokens zusammenfassen: 1+2−3·4+5^6^7·8−9 (Hier: Jedes Zeichen ist ein Token)
  2. 1 zur Ausgabe
  3. + auf den Stack
  4. 2 zur Ausgabe
  5. −:
    1. + zur Ausgabe
    2. − auf den Stack
  6. 3 zur Ausgabe
  7. · auf den Stack
  8. 4 zur Ausgabe
  9. +:
    1. · zur Ausgabe
    2. − zur Ausgabe
    3. + auf den Stack
  10. 5 zur Ausgabe
  11. ^ auf den Stack
  12. 6 zur Ausgabe
  13. ^ auf den Stack (^ ist rechtsassoziativ)
  14. 7 zur Ausgabe
  15. ·:
    1. ^ zur Ausgabe
    2. ^ zur Ausgabe
    3. · auf den Stack
  16. 8 zur Ausgabe
  17. −:
    1. · zur Ausgabe
    2. + zur Ausgabe
    3. − auf Stack
  18. 9 zur Ausgabe
  19. Ende: − zur Ausgabe

Ausgabe: 12+34·−567^^8·+9−

Explizit geklammert ([(1 + 2) − (3·4)] + {[5^(6^7)]·8}) − 9 ist dies möglicherweise einfacher nachzuvollziehen.

cos(1 + sin(ln(5) − exp(8))^2)

  1. Tokens zusammenfassen: cos ( 1 + sin ( ln ( 5 ) − exp ( 8 ) ) ^ 2 )
  2. cos auf den Stack
  3. ( auf den Stack
  4. 1 zur Ausgabe
  5. + auf den Stack
  6. sin auf den Stack
  7. ( auf den Stack
  8. ln auf den Stack
  9. ( auf den Stack
  10. 5 zur Ausgabe
  11. ):
    1. oberste ( vom Stack entfernen
    2. ln zur Ausgabe
  12. – auf den Stack
  13. exp auf den Stack
  14. ( auf den Stack
  15. 8 zur Ausgabe
  16. ):
    1. oberste ( vom Stack entfernen
    2. exp zur Ausgabe
  17. ):
    1. – zur Ausgabe
    2. oberste ( vom Stack entfernen
    3. sin zur Ausgabe
  18. ^ auf den Stack
  19. 2 zur Ausgabe
  20. ):
    1. ^ zur Ausgabe
    2. + zur Ausgabe
    3. oberste ( vom Stack entfernen
    4. cos zur Ausgabe
  21. Ende: Keine übrigen Elemente im Stack, also fertig!

Ausgabe: 15ln8exp−sin2^+cos