Parser der mathematische Ausdrücke vereinfacht

Hey C++ler,

in dem Interpreterbau Tutorial wird zwar ein AST generiert, leider ist es nicht möglich mit diesem Ausdrücke zu vereinfachen (5+Pi+1 wird in dem Fall ausgerechnet und nicht zu Pi+6 vereinfacht). Geht das mit dem Ansatz, dass die Nodes ihr Ergebnis selber rechnen und dann zurückgeben überhaupt? Wenn nicht, wie dann? Ohne AST?

Vielen Dank

Ein AST ist schon der richtige Ansatz.

Besser als ein binäres plus ist allerdings ein plus, das beliebig viele Argumente nimmt. Also Node Plus mit vector<Node> Operands; Dann kannst du Operands analysieren und vereinfachen was geht.

Auch musst du drüber nachdenken, wie du (1+pi)*2 in 2*1 + 2*pi vereinfachst. Im Grunde geht das genauso.

icarus2

Mit einem AST geht das. Google mal nach Constant Propagation und Constant Folding (oder etwas allgemeiner Dataflow Analysis).

Ich bin etwas unerfahren mit Parsern und Interpretern. Ist es praktischer, das ganze über eine eval() Funktion in jeder Node zu machen, oder einen Walker zu programmieren, der über den ganzen AST "geht" und evaluiert?

Kommt drauf an, wie viel du machen willst. Eine eval()-Funktion ist grundsätzlich am einfachsten, hat aber ihre Grenzen. Du willst eigentlich nicht die ganze Logik in den AST-Klassen unterbringen und Umbauen vom AST ist auch nicht so einfach (bei "(1+pi)*2" --> "2*1 + 2*pi" ändert der Top-Knoten von * in +).

Wenn du mehr als ein simples eval() willst, dann bau dir einen Visitor. Überlege dir ausserdem effiziente RTTI-Abfragen ("ist dieser Knoten vom Typ X?") -- dynamic_cast ist da auf Dauer langsam und umständlich.