Shunting-yard-Algorithmus

Zweck und Grundidee

Der Shunting-yard-Algorithmus, deutsch „Rangierbahnhof-Algorithmus“, ist ein Verfahren zur Umwandlung mathematischer Terme aus der Infixnotation in die umgekehrte polnische Notation oder in einen abstrakten Syntaxbaum. Bei der Infixnotation steht ein Operator, also ein Operationszeichen wie „+“ oder „·“, zwischen seinen Operanden. Der Algorithmus wurde von Edsger W. Dijkstra entwickelt.

Sein Kern besteht darin, einen Term Zeichen für Zeichen beziehungsweise Token für Token zu lesen. Zahlen werden unmittelbar in die Ausgabe übernommen. Operatoren werden zunächst in einem Stack zwischengespeichert. Ein Stack arbeitet nach dem LIFO-Prinzip („Last In, First Out“): Das zuletzt abgelegte Element wird zuerst wieder entnommen. Zusätzlich gibt es eine Input- und eine Outputqueue; eine Queue arbeitet nach dem FIFO-Prinzip („First In, First Out“).

Verarbeitung von Operatoren und Klammern

Trifft der Algorithmus auf ein Operationszeichen, prüft er die bereits im Operatorenstack gespeicherten Operatoren. Anhand der Operatorpräzedenz und der Operatorassoziativität wird entschieden, ob der neue Operator direkt auf den Stack kommt oder ob zuvor Operatoren vom Stack in die Ausgabe übertragen werden. Die Präzedenz beschreibt die Bindungsstärke: Eine höhere Präzedenz bedeutet eine stärkere Bindung. Die Assoziativität legt fest, in welcher Richtung gleichrangige Operatoren gruppiert werden.

Öffnende Klammern werden auf den Operatorstack gelegt, aber niemals in die Ausgabe geschrieben. Bei einer schließenden Klammer werden zunächst alle Stack-Elemente bis zur zugehörigen öffnenden Klammer in die Ausgabe verschoben. Die öffnende Klammer wird anschließend entfernt und nicht ausgegeben. Steht danach eine Funktion auf dem Stack, wird auch diese in die Ausgabe übernommen.

Wird beim Suchen nach einer öffnenden Klammer der Stack leer, ist der Eingabestring unvollständig. Die konkrete Fehlerbehandlung ist jedoch nicht Bestandteil des Algorithmus.

Pseudocode, Voraussetzungen und Grenzen

Der Ablauf lässt sich so zusammenfassen:

• Stack und Ausgabequeue anlegen und solange Tokens verfügbar sind, jeweils ein Token einlesen.
• Ist das Token eine Zahl, wird es direkt zur Ausgabe hinzugefügt.
• Ist es eine Funktion, kommt es auf den Stack.
• Bei einem Argumenttrennzeichen werden Stack-Elemente bis zur nächsten öffnenden Klammer in die Ausgabe verschoben. Ist der Stack vorher leer, liegt entweder ein falsch platziertes Argumenttrennzeichen vor oder der schließenden Klammer geht keine öffnende voraus.
• Bei einem Operator werden solange Operatoren vom Stack ausgegeben, wie der Stack nicht leer ist und die Präzedenz des neuen Operators kleiner als die Präzedenz des Stack-Operators ist oder beide Präzedenzen gleich sind und der neue Operator linksassoziativ ist. Danach wird der neue Operator auf den Stack gelegt.
• Bei einer schließenden Klammer werden Stack-Operatoren bis zur öffnenden Klammer ausgegeben. Die öffnende Klammer wird entfernt; eine anschließend auf dem Stack liegende Funktion wird ebenfalls ausgegeben.
• Nach dem Ende der Eingabe werden alle übrigen Stack-Elemente ausgegeben. Wird dabei noch eine öffnende Klammer gefunden, gibt es mehr öffnende als schließende Klammern.

Vorausgesetzt wird, dass der Parser alle Tokens korrekt erkennt und sie gültig sind. Benötigt werden insbesondere Funktionen zum Erkennen von vorzeichenbehafteten Zahlen, Funktionen, Argumenttrennzeichen und Operatoren sowie zum Feststellen von Operatorassoziativität und Operatorpräzedenz. Die Präzedenz einer Funktion ist maximal. Der Algorithmus behandelt nicht die Überlagerung der Zeichen „+“ und „−“ als Vorzeichen beziehungsweise als Operator. Ein Konflikt zwischen rechts- und linksassoziativen Operatoren gleicher Präzedenz wird ebenfalls nicht abgefangen. Für den Pseudocode werden sowohl ein lesender Zugriff auf die Stack-Spitze als auch das Entnehmen der Stack-Spitze vorausgesetzt.

Beispiele und Ergebnisse

Für die Beispiele gelten die Präzedenzen „(+,−) < (·,:) < (^) < Funktionen“. Gleichrangige Potenzoperatoren werden wegen der Rechtsassoziativität von „^“ von rechts nach links verarbeitet.

Beim Term „(3 + 4)(5 − 6)“ werden zunächst die Klammern und Operatoren auf den Stack gelegt, während die Zahlen 3, 4, 5 und 6 in dieser Reihenfolge ausgegeben werden. Nach der ersten schließenden Klammer wird „+“ ausgegeben, nach der zweiten „−“. Zwischen den beiden geklammerten Ausdrücken wird ein implizites „·“ erkannt und auf den Stack gelegt. Am Ende lautet die Ausgabe „34+56−·“.

Beim Term „1 + 2 − 3 · 4 + 5^6^7 · 8 − 9“ werden bei „−“ zunächst „+“, bei dem späteren „+“ zunächst „·“ und „−“ ausgegeben. Die beiden Potenzoperatoren bleiben wegen der Rechtsassoziativität zunächst auf dem Stack. Die Ausgabe lautet „12+34·−567^^8·+9−“. Die explizite Klammerung „([(1 + 2) − (3·4)] + {[5^(6^7)]·8}) − 9“ macht diese Reihenfolge nachvollziehbar.

Beim Funktionsterm „cos(1 + sin(ln(5) − exp(8))^2)“ werden Funktionen wie „cos“, „sin“, „ln“ und „exp“ auf dem Stack gespeichert und nach ihren schließenden Klammern ausgegeben. Das Ergebnis ist „15ln8exp−sin2^+cos“; danach enthält der Stack keine übrigen Elemente mehr.