Termaritmethik

[RazorX]

Servus,

ich brauch mal einen kleinen Denkanstoss. Bis lang habe ich einen kleinen Parser geschrieben, der einen geklammerten (auch verschachtelten) Term erkennen kann, sowie in einen Syntaxbaum überträgt. Aufgebaut ist der Baum wie folgt:

Code: Alles auswählen

Beispielterm: 2 + 3*(2-1)
Baum:
......+
..../...\
...2.....*
......./...\
......3.....-
........../...\
.........2.....1

Bis lang hab ich es so gemacht, das am Ende der Äste immer ein Bruch mit dem entsprechenden Wert hängt. Nun will ich aber vorallem mit unbekannten rechnen können, heißt auch Terme vereinfachen. Den Baum auf Variablen zu erweitern ist nicht das Problem, auszurechnen wäre das durch Parameterübergabe immer noch. Jedoch geht es nun um das explizite Vereinfachen eines Terms. Mit Bezug auf den Gauss Jordan Algorithmus möchte ich es ermöglichen mit Unbekannten rechnen zu können um dann Entscheidungsbäume zu erstellen.

Code: Alles auswählen

Aus: 2*(1-r)+(-3)*(1+r)
Soll werden: - 5r - 1

Ist die Art der bisherigen Termspeicherung sinnvoll? Wie würde die Arithmetik dazu aussehen? Kennt jemand nützliche Quellen zu dem Thema (bin leider bis jetzt nur auf einfache Parser für Variablen mit Wertübergabe gestoßen)?

Mit freundlichen Grüßen

RazorX

[Krishty]

Ist die Art der bisherigen Termspeicherung sinnvoll? Wie würde die Arithmetik dazu aussehen?

Im Compiler-Bau benutzt man für Optimierungen üblicherweise die Static Single Assignment Form – aber da werden vor allem weniger abstrakte Vereinfachungen durchgeführt; deine Syntaxbaumform dürfte dafür besser geeignet sein.

Ich würde jetzt einfach abwechselnd Ausklammern (weil sich nur klammerlose Therme falten lassen) und Constant Propagation drüberlaufen lassen, bis sich nichts mehr vereinfachen lässt – ich kenne mich aber nicht wirklich mit sowas aus.

Gruß, Ky

[eXile]

So wie ich das sehe, ergeben deine Terme immer Polynome in den auftretenden Variablen. Du kannst also deinen Term als die Summe bzw. das Produkt von Polynomen ansehen, und muss entsprechend nur die symbolische Addition und Multiplikation von Polynomen korrekt implementieren, und hast am Ende ein vollständig ausmultipliziertes Polynom stehen.