infix, präfix zu postfix bei OOP-Syntax |
09.07.2013, 10:26 | Auf diesen Beitrag antworten » |
Hobbie | infix, präfix zu postfix bei OOP-Syntax Meine Frage: Ausdrücke mit infix-Operatoren usw. sollen in die postfix-Form umgewandelt werden. Z.B. wird "sin(a+2*b)" zu "a 2 b * + sin". Man kann dafür z.B. den shunting-yard-Algorithmus verwenden. Dabei tritt jedoch bei OOP-Syntax ein Problem auf. Der Ausdruck "a.p(x)" wird zu "x a . p". Der Ausdruck "(a+4)->p(x)" wird zu "x a 4 + -> p". Normalerweise wird der Funktions-Bezeichner auf den Operator-Stapel gepackt. In diesem Fall müsste jedoch ein ganzer Ausdruck auf den Operator-Stapel gepackt werden. Meine Frage ist jetzt wie ich den shunting-yard-Algorithmus dahingehend modifizieren kann. Es ist natürlich auch wünschenswert, dass man keine großen Laufzeiteinbußen hinnehmen muss, wenn der besagte Fall garnicht eintritt. Meine Ideen: Ich habe mir überlegt einen zweiten Stapel stack2 zu verwenden. Das was der Algorithmus ausspuckt wird nicht zur Ausgabe hinzugefügt sondern zu stack2.top. Erst am Ende wird stack2.top zur Ausgabe hinzugefügt. Gehört zum Ausdruck jedoch ein Prozedur-Aufruf so wird stack2.top auf den Operatorstack gepackt. Offenbar muss bei verschachtelten Ausdrücken der Stackpointer von stack2 incrementiert werden. So die Idee. Vielleicht sollte ich eine andere Art von Parser verwenden. Ich weiß nicht. Wenn ich einen Syntax-Baum mache, dann könnte ich eventuell einfach zwei Knoten vertauschen und fertig. Aber das ist bäh wegen Allokations-Aufwand Baum vs. Stapel von Referenzen. |
|
|