Diskussion:Shunting-yard-Algorithmus

Beispiele vonnöten!

Ich bin der Meinung, dass man das ganze Veranschaulichen kann, indem man ein Beispiel einfügt, sodass zumindest erkennbar ist, was bei diesem Algorithmus zu was wird. Das ist in dem englischen Artikel http://en.wikipedia.org/wiki/Shunting-yard_algorithm ganz gut gelöst, finde ich. --Nico 17:00, 29. Jul. 2010 (CEST)

Ich habe mir jetzt einfach mal drei Bsp. ausgedacht und überprüft und hoffe sie sind allgemein genug. Argumenttrennzeichen habe ich zunächst mal weggelassen, kommt aber sicher noch. --Spezialist^D 01:30, 18. Sep. 2013 (CEST)

Divisionsoperator als Bruchstrich oder nicht

Man sollte vielleicht anmerken, dass im Pseudocode der Divisionsoperator (linksassotiativ, gleiche Präzedenz wie Multiplikationsoperator) als Bruchstrich gesehen wird (was einer Klammerung von Zähler und Nenner entspricht).

Die Eingabe von 6 / 2 * 3 führt zum Ergebnis 6 2 3 * /

Möchte man das nicht (sondern 6 2 / 3 *) und den Divisionsoperator wie (in Programmiersprachen) üblich verwenden, so muss der entsprechende Teil im Pseudocode folgendermaßen lauten:

 WENN Token IST-Operator
   SOLANGE Stack IST-NICHT-LEER UND Stack-Spitze IST Operator UND
     Präzedenz von Token IST-KLEINERGLEICH Präzedenz von Stack-Spitze:
     Stack-Spitze ZU Ausgabe.
   ENDESOLANGE
   Token ZU Stack.
 ENDEWENN (nicht signierter Beitrag von Masterle (Diskussion | Beiträge) 08:39, 17. Okt. 2013 (CEST))

BIS/SOLANGE

Mir kommt es komisch vor, dass die Anweisung an der einen Stelle SOLANGE heißt und an der anderen BIS. Ich denke, ich verstehe den Unterschied (BIS ist wie ein SOLANGE NICHT) aber ich habe erstmal gedacht, dass es sich um eine nachprüfende Schleife handelt. Ich würde es so lösen wie in der englischsprachigen Version, wo es überall WHILE heißt.

Fehler im Algorithmus?

Ich habe den Algorithmus implementiert und errechne dann mit der RPN das Ergebnis. Viele Rechnungen führen zum richtigen Ergebnis.

Allerdings wird zu infix 4-5+6 die RPN 4 5 6 + - erzeugt, was zum Ergebnis -7 führt, wobei dieses doch 5 ist.

Erwartet hätte ich die RPN 4 5 - 6 +. Diese erreiche ich jedoch mit dem hier im Pseudocode festgehaltenen Algorithmus nicht. Liegt der Fehler bei mir oder tatsächlich hier im Pseudocode?

Hier die Schritte wie ich sie nach diesem Algortihmus verstehe ( und wie es leider nicht funktioniert):

1. Token 4 zur Ausgabe
2. Token - auf den Stack
3. Token 5 zur Ausgabe
4. Da Token + nicht linksassoziativ ist, wird die Stack-Spitze (Minus operator) nicht ausgegeben
5. Token + landet auf dem Stack
6. Token 6 zur Ausgabe
7. Der Stack wird Top-Down abgeräumt:
   1. Token + zur Ausgabe
   2. Token - zur Ausgabe

Update: Dijkstra schrieb in https://www.cs.utexas.edu/~EWD/MCReps/MR35.PDF auf Seite 28:

"Priority 9: + -
Priority 10: * /
[...]
Incoming operators receive their priority numbers and are then sent to the translator stack, but before the latter happens, operators in the translator stack are transported from it to the output as long as their priority number '''is greater then or equal to''' the priority number of the new operator."

Da steht nichts von linksassoziativ. Wenn ich "Token IST-linksassoziativ UND" aus dem Pseudocode entferne, funktioniert der Algorithmus in all meinen Testfällen.

(nicht signierter Beitrag von 77.12.84.128 (Diskussion) 12:10, 14. Jan. 2021 (CET))

Beschreibung und Beispiel was als Token zu verstehen ist

Hallo, ich fänd es schön, wenn zum Thema wie eine Formel in Tokens zerlegt wird noch ein kleiner Abschnitt hinzu kommen könnte. Die Zerlegung in die Tokens von "sin(x) * cos(y) - 3*Pi" ist durch das 3. Beispiel klar. ("sin" "(" "x" ")" "*" "cos" "(" "y" ")" "-" "3" "*" und "Pi")

Aber wie sieht es mit Zahlen kleiner 0 aus? Also z.B. "sin(-x) * cos(-1.5 * Pi)" Ist hier "-x" und "-1.5" jeweils 1 Token? Wenn ja, wie könnte da der Pseudocode aussehen um dies zu ermitteln? (nicht signierter Beitrag von 212.18.21.242 (Diskussion) 13:57, 7. Jul. 2021 (CEST))