imported>SweetWood: Bildlegende ohne Schlusspunkt; Wikicode optimiert; Wikilinks eingefügt; Klarstellungen; Rechtschreibung; Vereinheitlichungen; Formelsatz optimiert

2024-08-28T08:52:22Z

Bildlegende ohne Schlusspunkt; Wikicode optimiert; Wikilinks eingefügt; Klarstellungen; Rechtschreibung; Vereinheitlichungen; Formelsatz optimiert

Neue Seite

[[Datei:Shunting yard.svg|400px|mini|Grafische Illustration des Algorithmus als 3-Weg-Weichenstellung]]
Der '''Shunting-yard-Algorithmus''' ([[Deutsche Sprache|deutsch]]: Rangierbahnhof-Algorithmus) ist eine Methode, um mathematische [[Term]]e von der [[Infixnotation]] in die [[umgekehrte polnische Notation]] oder in einen [[Abstrakter Syntaxbaum|abstrakten Syntaxbaum]] zu überführen. Der [[Algorithmus]] wurde von [[Edsger W. Dijkstra]] erfunden und mit {{enS|shunting yard|de=Rangierbahnhof}} benannt, weil er in seiner Arbeitsweise an einen [[Rangierbahnhof]] erinnert.

== Funktionsweise ==
Der Shunting-yard-Algorithmus benötigt für die Konversion sowohl eine [[Eingabe und Ausgabe|Input-]] als auch eine Output[[Warteschlange (Datenstruktur)|queue]] sowie einen [[Stapelspeicher|Stack]], der für das Zwischenspeichern der [[Operator (Mathematik)|Operator]]en benötigt wird. Der Input[[Zeichenkette|string]] wird zeichenweise gelesen, wobei alle [[Zahl]]en 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 [[Klammer (Zeichen)|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 [[Ausnahmebehandlung|Fehlerbehandlung]] nicht durch den Algorithmus definiert wird.

== Im Detail ==
Es folgt ein deutscher [[Pseudocode]], der in die meisten [[Programmiersprache]]n einfach übersetzt und angepasst werden kann.

[[Stapelspeicher|Stack]] (mit [[Last In – First Out|LIFO]]-Prinzip) sowie Ausgabe[[Warteschlange (Datenstruktur)|queue]] (mit [[First In – First Out|FIFO]]-Prinzip) anlegen.
'''SOLANGE''' Tokens verfügbar sind:
Token einlesen.
'''WENN''' Token IST-Zahl:
Token ZU Ausgabe.
'''ENDEWENN'''
'''WENN''' Token IST-Funktion:
Token ZU Stack.
'''ENDEWENN'''
'''WENN''' Token IST-Argumenttrennzeichen:
'''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'''
([[Operatorrangfolge|Präzedenz]] von Token IST-KLEINER Präzedenz von Stack-Spitze '''ODER'''
[[Operatorrangfolge|Präzedenz]] von Token IST-GLEICH Präzedenz von Stack-Spitze '''UND'''
Token IST-[[Operatorassoziativität|linksassoziativ]])
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-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 [[Tokenisierung|Token]]s vom [[Parser]] richtig erkannt werden und gültig sind. Insbesondere die Überlagerung ([[Vorzeichen (Zahl)|Vorzeichen]] versus [[Operator (Mathematik)|Operator]]) 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 (vorzeichenbehafteten) Zahlen
* Erkennen von [[Funktion (Mathematik)|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 ==
Die folgenden in Infixnotation gegebenen Rechnungen sollen umgeformt werden. Es wird dokumentiert, was geschieht.

Präzedenzen: (<code>[[Addition|+]]</code>,<code>[[Subtraktion|−]]</code>) < (<code>[[Multiplikation|·]]</code>,<code>[[Geteiltzeichen|:]]</code>) < (<code>[[Potenz (Mathematik)|^]]</code>) < Funktionen

=== (3 + 4)(5 − 6) ===
# Tokens zusammenfassen: <code>(</code><code>3</code><code>+</code><code>4</code><code>)</code><code>(</code><code>5</code><code>−</code><code>6</code><code>)</code> (Hier: Jedes Zeichen ist ein Token)
# <code>(</code> auf den Stack
# <code>3</code> zur Ausgabe
# <code>+</code> auf den Stack
# <code>4</code> zur Ausgabe
# <code>)</code>:
## <code>+</code> zur Ausgabe
## <code>(</code> vom Stack entfernen
# Operator erwartet, aber <code>(</code> gefunden:
## implizites <code>·</code> auf den Stack
## <code>(</code> auf den Stack
# <code>5</code> zur Ausgabe
# <code>−</code> auf den Stack
# <code>6</code> zur Ausgabe
# <code>)</code>:
## <code>−</code> zur Ausgabe
## <code>(</code> vom Stack entfernen
# Ende: <code>·</code> zur Ausgabe

Ausgabe:<code>3</code><code>4</code><code>+</code><code>5</code><code>6</code><code>−</code><code>·</code>

=== 1 + 2 − 3 · 4 + 5^6^7 · 8 − 9 ===
# Tokens zusammenfassen: <code>1</code><code>+</code><code>2</code><code>−</code><code>3</code><code>·</code><code>4</code><code>+</code><code>5</code><code>^</code><code>6</code><code>^</code><code>7</code><code>·</code><code>8</code><code>−</code><code>9</code> (Hier: Jedes Zeichen ist ein Token)
# <code>1</code> zur Ausgabe
# <code>+</code> auf den Stack
# <code>2</code> zur Ausgabe
# <code>−</code>:
## <code>+</code> zur Ausgabe
## <code>−</code> auf den Stack
# <code>3</code> zur Ausgabe
# <code>·</code> auf den Stack
# <code>4</code> zur Ausgabe
# <code>+</code>:
## <code>·</code> zur Ausgabe
## <code>−</code> zur Ausgabe
## <code>+</code> auf den Stack
# <code>5</code> zur Ausgabe
# <code>^</code> auf den Stack
# <code>6</code> zur Ausgabe
# <code>^</code> auf den Stack (<code>^</code> ist rechtsassoziativ)
# <code>7</code> zur Ausgabe
# <code>·</code>:
## <code>^</code> zur Ausgabe
## <code>^</code> zur Ausgabe
## <code>·</code> auf den Stack
# <code>8</code> zur Ausgabe
# <code>−</code>:
## <code>·</code> zur Ausgabe
## <code>+</code> zur Ausgabe
## <code>−</code> auf Stack
# <code>9</code> zur Ausgabe
# Ende: <code>−</code> zur Ausgabe

Ausgabe: <code>1</code><code>2</code><code>+</code><code>3</code><code>4</code><code>·</code><code>−</code><code>5</code><code>6</code><code>7</code><code>^</code><code>^</code><code>8</code><code>·</code><code>+</code><code>9</code><code>−</code>

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) ===
# Tokens zusammenfassen: <code>cos</code> <code>(</code> <code>1</code> <code>+</code> <code>sin</code> <code>(</code> <code>ln</code> <code>(</code> <code>5</code> <code>)</code> <code>−</code> <code>exp</code> <code>(</code> <code>8</code> <code>)</code> <code>)</code> <code>^</code> <code>2</code> <code>)</code>
# <code>cos</code> auf den Stack
# <code><nowiki>(</nowiki></code> auf den Stack
# <code>1</code> zur Ausgabe
# <code>+</code> auf den Stack
# <code>sin</code> auf den Stack
# <code><nowiki>(</nowiki></code> auf den Stack
# <code>ln</code> auf den Stack
# <code><nowiki>(</nowiki></code> auf den Stack
# <code>5</code> zur Ausgabe
# <code><nowiki>)</nowiki></code>:
## oberste <code><nowiki>(</nowiki></code> vom Stack entfernen
## <code>ln</code> zur Ausgabe
# <code>–</code> auf den Stack
# <code>exp</code> auf den Stack
# <code><nowiki>(</nowiki></code> auf den Stack
# <code>8</code> zur Ausgabe
# <code><nowiki>)</nowiki></code>:
## oberste <code><nowiki>(</nowiki></code> vom Stack entfernen
## <code>exp</code> zur Ausgabe
# <code><nowiki>)</nowiki></code>:
## <code>–</code> zur Ausgabe
## oberste <code><nowiki>(</nowiki></code> vom Stack entfernen
## <code>sin</code> zur Ausgabe
# <code>^</code> auf den Stack
# <code>2</code> zur Ausgabe
# <code><nowiki>)</nowiki></code>:
## <code>^</code> zur Ausgabe
## <code>+</code> zur Ausgabe
## oberste <code><nowiki>(</nowiki></code> vom Stack entfernen
## <code>cos</code> zur Ausgabe
# Ende: Keine übrigen Elemente im Stack, also fertig!

Ausgabe: <code>1</code><code>5</code><code>ln</code><code>8</code><code>exp</code><code>−</code><code>sin</code><code>2</code><code>^</code><code>+</code><code>cos</code>

== Weblinks ==
* [https://www.cs.utexas.edu/~EWD/MCReps/MR35.PDF Ursprüngliche Beschreibung des Algorithmus] (PDF; 1,1 MB; englisch)

[[Kategorie:Algorithmus]]

Shunting-yard-Algorithmus - Versionsgeschichte

imported>SweetWood: Bildlegende ohne Schlusspunkt; Wikicode optimiert; Wikilinks eingefügt; Klarstellungen; Rechtschreibung; Vereinheitlichungen; Formelsatz optimiert