Der letzte Beitrag |
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. |
|
|