Shunting-yard-Algorithmus
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 Vorlage:"-en 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 ein Stack, der für das zwischenspeichern der Operatoren benötigt wird. Der Input-Stringwird Zeichenweise gelesen, wobei alle Zahlen direkt und in der selben Reihenfolge in die Ausgabevariable geschreiben 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.