- 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 Dijkstra erfunden und mit “shunting yard” (deutsch: „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 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.
Weblinks
Wikimedia Foundation.
