Wie überführt man am Geschicktesten einen String, der in Infix Notation (3 + 4) vorliegt in eine Prefix-Notation (+ 3 4). Es sollen folgende Rechenoperationen unterstützt werden +, -, *, /. Die Programmiersprache ist C#
Ein sehr eleganter Algorithmus, um algebraische Ausdrücke in Infix-Notation in einen Ausdruck in Postfix-Notation oder einen Abstrakten Syntax-Baum zu überführen, wurde von Edsger Wybe Dijkstra entwickelt und nennt sich Shunting-Yard-Algorithmus (Rangier-Bahnhof) nach der Art und Weise, wie die Operatoren und Operanden zwischen der Ausgabe-Queue und dem Operator-Stapel hin und her verschoben werden.
Der Shunting-Yard-Algorithmus sollte sich eigentlich recht einfach für Präfix-Notation anpassen lassen. Auf den ersten Blick sieht es so aus, als müsste man nur die Ausgabe-Queue "umdrehen", sprich einen Stapel statt einer Queue verwenden.
EDIT: Es stellt sich natürlich heraus, dass das ganze nicht so einfach ist. Eigentlich hätte ich das gleich sehen müssen, denn
Infix: a / b
Postfix: a b /
Präfix: / a b
Präfix-Notation ist also mitnichten einfach nur Postfix-Notation rückwärts. Es reicht also nicht, die Datenstruktur umzudrehen.
Ich habe ein Beispiel gefunden, ist allerdings eine "Infix Notification to Reverse Polish Notification", was aber relativ leicht abzuändern ist (ist ja schließlich nur reversiert und muss daher nur getauscht werden).
