Shunting-yard-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
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 “shunting yard” (deutsch: „Rangierbahnhof“) benannt, weil er in seiner Arbeitsweise an einen Rangierbahnhof erinnert.

Funktionsweise[Bearbeiten]

Der Shunting-yard-Algorithmus benötigt für die Konversion sowohl eine Input- als auch eine Outputvariable sowie einen Stack, der für das Zwischenspeichern der Operatoren benötigt wird. Der Input-String 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[Bearbeiten]

Es folgt deutscher Pseudo-Code, der in die meisten Programmiersprachen einfach übersetzt und angepasst werden kann.

  • Stack mit LIFO-Prinzip und Ausgabe-Queue anlegen.
  • SOLANGE Tokens verfügbar sind:
  • Token einlesen.
  • WENN Token IST-Zahl:
  • Token ZU Ausgabe.
  • ENDEWENN
  • WENN Token IST-Funktion:
  • Token ZU Stack.
  • 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
ENTWEDER Token IST-linksassoziativ UND Präzedenz von Token IST-KLEINERGLEICH Präzedenz von Stack-Spitze
ODER Präzedenz von Token IST-KLEINER Präzedenz von Stack-Spitze:
  • 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-NICHT-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 richtig erkannt werden und gültig sind. Insbesondere die Überlagerung 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 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[Bearbeiten]

Die folgenden in Infix-Notation gegebenen Rechnungen sollen umgeformt werden. Es wird dokumentiert, was geschieht.

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

(3 + 4)(5 − 6)[Bearbeiten]

  1. Tokens zusammenfassen: hier nicht illustriert, da alle einzelnen Zeichen je ein Token sind.
  2. öffnende Klammer auf den Stack.
  3. 3 zur Ausgabe
  4. Plus-Operator auf den Stack
  5. 4 zur Ausgabe
  6. schließende Klammer:
    1. Plus zur Ausgabe
    2. öffnende Klammer vom Stack entfernen
  7. (impliziter) Mal-Operator auf den Stack
  8. öffnende Klammer auf den Stack
  9. 5 zur Ausgabe
  10. Minus-Operator auf den Stack
  11. 6 zur Ausgabe
  12. schließende Klammer:
    1. Minus zur Ausgabe
    2. öffnende Klammer vom Stack entfernen
  13. Ende: Mal zur Ausgabe

Da hier jedes Token einzigartig ist, ist die Angabe, wo es sich befindet, unnötig.

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

  1. Tokens zusammenfassen: hier nicht illustriert, da alle einzelnen Zeichen je ein Token sind.
  2. 1 zur Ausgabe
  3. Plus auf den Stack
  4. 2 zur Ausgabe
  5. Minus:
    1. Plus zur Ausgabe
    2. Minus auf den Stack
  6. 3 zur Ausgabe
  7. Mal auf den Stack
  8. 4 zur Ausgabe
  9. Plus:
    1. Mal zur Ausgabe
    2. Minus zur Ausgabe
    3. Plus auf den Stack
  10. 5 zur Ausgabe
  11. Potenz auf den Stack
  12. 6 zur Ausgabe
  13. Potenz auf den Stack (Potenz rechtsassoziativ)
  14. 7 zur Ausgabe
  15. Mal:
    1. Potenzen zur Ausgabe
    2. Mal auf den Stack
  16. 8 zur Ausgabe
  17. Minus:
    1. Mal zur Ausgabe
    2. Plus (zw. 4 und 5) zur Ausgabe
    3. Minus auf Stack
  18. 9 zur Ausgabe
  19. Ende: Minus zur Ausgabe

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)[Bearbeiten]

  1. Tokens zusammenfassen: [cos] ( 1 + [sin] ( [ln] ( 5 ) − [exp] ( 8 ) ) ^ 2 )
  2. [cos] auf den Stack
  3. öffnende Klammer auf den Stack
  4. 1 zur Ausgabe
  5. Plus-Operator auf den Stack
  6. [sin] auf den Stack
  7. öffnende Klammer auf den Stack
  8. [ln] auf den Stack
  9. öffnende Klammer auf den Stack
  10. 5 zur Ausgabe
  11. schließende Klammer:
    1. oberste öffnende Klammer vom Stack entfernen
    2. [ln] zur Ausgabe
  12. Minus-Operator auf den Stack
  13. [exp] auf den Stack
  14. öffnende Klammer auf den Stack
  15. 8 zur Ausgabe
  16. schließende Klammer:
    1. oberste öffnende Klammer vom Stack entfernen
    2. [exp] zur Ausgabe
  17. schließende Klammer:
    1. Minus-Operator zur Ausgabe
    2. oberste öffnende Klammer vom Stack entfernen
    3. [sin] zur Ausgabe
  18. Potenz-Operator auf den Stack
  19. 2 zur Ausgabe
  20. schließende Klammer:
    1. Potenz-Operator zur Ausgabe
    2. Plus-Operator zur Ausgabe
    3. oberste öffnende Klammer vom Stack entfernen
    4. [cos] zur Ausgabe
  21. Ende: Keine übrigen Elemente im Stack -> Fertig!

Weblinks[Bearbeiten]