Shunting-Yard-Algorithmus ist ein Verfahren von Edsger W. Dijkstra (um 1961, im Zusammenhang mit ALGOL-Compilern entwickelt), das mathematische Ausdrücke in Infix-Schreibweise — also der gewohnten Form wie 3 + 4 * 2 — in die Postfix-Schreibweise (auch Reverse Polish Notation, RPN, oder UPN) umwandelt. Der Name erinnert an einen Rangierbahnhof (englisch shunting yard): Operanden und Operatoren werden wie Waggons über Gleise (Stapel) sortiert, bis die richtige Reihenfolge feststeht.
Die zwei Hilfsstrukturen
- Output-Queue: sammelt das Ergebnis in der richtigen Postfix-Reihenfolge.
- Operator-Stack: hält Operatoren und Klammern zwischen, bis sie an der Reihe sind.
Das Verfahren läuft in einem einzigen Durchgang von links nach rechts:
Operand -> direkt in die Output-Queue
Operator O -> erst alle Operatoren mit
höherer/gleicher Präzedenz
vom Stack in die Output-Queue,
dann O auf den Stack
öffnende Klammer -> auf den Stack
schließende Klammer -> vom Stack bis zur öffnenden
Klammer in die Output-Queue
Ende -> Rest des Stacks leerenBeispiel: 3 + 4 * 2
Das * hat höhere Präzedenz als +. Deshalb bleibt das + zunächst auf dem Stack, bis das * verarbeitet ist. Das Ergebnis ist 3 4 2 * + — in Postfix. Die Auswertung dieser Form ist trivial: Werte auf einen Stack legen, bei jedem Operator die obersten zwei Werte verknüpfen. Genau das machten klassische RPN-Taschenrechner von Hewlett-Packard.
Präzedenz, Assoziativität und Klammern
Für links-assoziative Operatoren (wie +, -, *, /) werden bei gleicher Präzedenz die bestehenden Operatoren vom Stack geholt. Für rechts-assoziative Operatoren (wie die Potenz ^) bleibt der Operator liegen, bis ein stärkerer kommt. Klammern überschreiben die Präzedenz vollständig: (3 + 4) * 2 ergibt 3 4 + 2 *. Der Algorithmus ist mit O(n) linear in der Eingabelänge — jeder Token wird genau einmal verschoben.
Einsatzgebiete
Der Shunting-Yard-Algorithmus steckt in Formel-Engines, Spreadsheet-Programmen, Interpretern für mathematische Ausdrücke und RPN-Rechnern. Er ist eine Alternative zum Pratt-Parser: Beide lösen das Präzedenz-Problem, der Shunting-Yard erzeugt aber eine flache Postfix-Liste statt eines Strukturbaums. Wer daraus einen Syntaxbaum braucht, kann die Postfix-Form anschließend mit einem Stack in einen Baum überführen.
Verwandte Themen: Parser, Syntax, Queue, rekursiver Abstieg.