Mathematische Gleichungen/Terme vereinfachen
-
Hi,
ich wollte wollte einfach mal probieren, ob ich es schaffe mit Hilfe des Artikels zum Interpreterbau eine Software zu schreiben die mathematische Terme verinfacht. Der Term sin(4) ist nicht weiter vereinfachbar, der Term sin(5+5) hingegen schon.
Mein Ansatz war einen AST aufzubauen (wie im Artikel beschrieben) und dann eine eval_string() und eine vereinfachbar() Funktion zur Node-Klasse hinzuzufügen. Die vereinfachbar() Funktion gibt zurück ob diese Node verinfachbar ist, die eval_string() Funktion gibt (je nach Klasse und ob die zwei Operanden vereinfachbar sind) den vereinfachten Wert (als string) oder den unvereinfachten Wert zurück.
Hier ein kleines Beispiel:
sin(2+3)*10
Der AST dazu sieht so aus:
NodeMul | | NodeFunc(sin) NodeNumber (10) | NodeAdd | | NodeNumber (2) NodeNumber (3)NodeAdd wird vereinfacht (da möglich), NodeFunc wird nicht verinfacht (da nicht möglich) und NodeMul kann nicht wirklich verinfacht werden, da NodeFunc nicht vereinfach werden konnte. Am ende kommt sin(5)*10 raus.
Soweit auch gut. Allerdings hat mein "Algorithmus" Probleme mit 5+pi+5 (nur zur Klarstellung, jede Rechnung mit pi kann nicht vereinfacht werden).
Der generierte AST sieht so aus:
NodeAdd | | NodeAdd NodeNumber (5) | | NodeIdent(pi) NodeNumber (3)Der Algorithmus verinfacht nun garnicht mehr (das zweite NodeAdd lässt sich dank Pi nicht vereinfachen, das erste lässt sich nicht vereinfachen, wegen dem zweiten NodeAdd).
Ist dies ein Anwedungsfall in dem AST an ihre Grenzen stoßen, oder hab ich eine einfache Lösungsmöglichkeit für dieses Problem übersehen? Wenn dieses Problem mit ASTs nicht (einfach) gelöst werden kann, wie soll ich es dann versuchen?
Vielen Dank
-
Du koenntest "gleichwertige" Operatoren zusammenfassen zu einem Knoten mit mehr als einem Kind, z.B. statt verschachtelte Additionen, nur ein Knoten, der ein Array mit n Summanden hat. Zusaetzlich koenttest du dann auch noch Addition und Subtraktion zusammenfassen und z.B. durch ein boolean oder einen Multiplikator kennzeichnen, um welche Art Knoten es sich handelt.
Dann kannst du bestimmte Muster vorgeben, die mehr als eine Ebene umfassen, um z.B. nach Distributivgesetzen umzuformen oder einfach nach ein paar Regeln ausprobieren und dann das Programm die kuerzere Fassung auswaehlen lassen.
-
-Math- schrieb:
Mein Ansatz war einen AST aufzubauen (wie im Artikel beschrieben) und dann eine eval_string() und eine vereinfachbar() Funktion zur Node-Klasse hinzuzufügen.
Hört sich komisch an. Du solltest an der Stelle nicht mit Strings arbeiten, sondern wieder AST Nodes zurückgeben. Aus NodeAdd mit den zwei NodeNumber Objekten wird ein neuer NodeNumber Objekt. Einen String kannst du danach immer noch draus basteln.
"Vereinfachen" gefällt mir hier als Begriff auch nicht so ganz, das ist ja eher eine Optimierung und man könnte auch ähnliche Optimierungen einbauen.Zu deinem eigentlichen Problem, das kommt auf den Aufbau an. Das hat jetzt nichts mit AST oder nicht AST zu tun. Kannst du irgendwie erkennen, dass "Pi" eine Konstante ist? Wenn ja, kannst du das ganz einfach vereinfachen, wenn du das nicht erkennen kannst, dann kommst du hier einfach nicht weiter.
Ich würde sagen, auch wenn du Variablen unterstützt, wäre es ok, eine hartkodierte Liste mit reservierten Namen zu pflegen, wo auch pi vorkommt. Dann weiß dein Optimierer, dass es eine Konstante ist.
-
Marthog schrieb:
Du koenntest "gleichwertige" Operatoren zusammenfassen zu einem Knoten mit mehr als einem Kind, z.B. statt verschachtelte Additionen, nur ein Knoten, der ein Array mit n Summanden hat.
Hört sich leider einfacher an, als es ist. Dafür muss ich halt nochmal den Parser umschreiben, aber ich denke auch, dass das die einzige Lösung ist.
Mechanics schrieb:
Hört sich komisch an. Du solltest an der Stelle nicht mit Strings arbeiten, sondern wieder AST Nodes zurückgeben. Aus NodeAdd mit den zwei NodeNumber Objekten wird ein neuer NodeNumber Objekt.
Das würde mein Problem leider nicht wirklich lösen, am Ende hätte ich genau den selben AST. Beide NodeAdds lassen sich nämlich, wenn man sie jeweils alleine sieht tatsächlich nicht optimieren. Erst wenn man sie beide sieht, sieht man, das vereinfachen möglich ist.
Mechanics schrieb:
Zu deinem eigentlichen Problem, das kommt auf den Aufbau an. Das hat jetzt nichts mit AST oder nicht AST zu tun. Kannst du irgendwie erkennen, dass "Pi" eine Konstante ist? Wenn ja, kannst du das ganz einfach vereinfachen, wenn du das nicht erkennen kannst, dann kommst du hier einfach nicht weiter.
Ja, ich kann erkennen das Pi eine Konstante ist (Pi wird in einer NodeIdent gespeichert, im Gegensatz zu normalen Nummern, die werden in einer NodeNumber gespeichert. Leider versteh ich nicht ganz, wie ich den optimieren kann. Dazu müsste ich eine große NodeAdd einführen, die alle Summanden enthält, was ich eigentlich vermeiden wollte.
Vielen Dank
-
Ich versteh deine Probleme irgendwie nicht. Wieso müsstest du den Parser umbauen, um den Vorschlag von Marthog zu implementieren? Das kannst du alles ausgehend von deinem AST machen. Der Parser erstellt den Baum so wie jetzt, nur fasst du die Knoten nachträglich zusammen.
-Math- schrieb:
Mechanics schrieb:
Hört sich komisch an. Du solltest an der Stelle nicht mit Strings arbeiten, sondern wieder AST Nodes zurückgeben. Aus NodeAdd mit den zwei NodeNumber Objekten wird ein neuer NodeNumber Objekt.
Das würde mein Problem leider nicht wirklich lösen, am Ende hätte ich genau den selben AST. Beide NodeAdds lassen sich nämlich, wenn man sie jeweils alleine sieht tatsächlich nicht optimieren. Erst wenn man sie beide sieht, sieht man, das vereinfachen möglich ist.
Inwiefern widerspricht das dem, was ich geschrieben habe?
Wenn Pi eine Konstanze ist, kannst sie doch einfach gleich auflösen und einen neuen NumberNode erstellen, wo der berechnete Wert drinsteht, genauso als ob das von Anfang an zwei NumberNodes gewesen wären.
-
-Math- schrieb:
Marthog schrieb:
Du koenntest "gleichwertige" Operatoren zusammenfassen zu einem Knoten mit mehr als einem Kind, z.B. statt verschachtelte Additionen, nur ein Knoten, der ein Array mit n Summanden hat.
Hört sich leider einfacher an, als es ist. Dafür muss ich halt nochmal den Parser umschreiben, aber ich denke auch, dass das die einzige Lösung ist.
Musst Du nicht. Aus dem Parser kann doch ein Binärbaum rauskommen und der Optimierer vereinfacht den dann danach.
Aber was ist "vereinfachen"? Wird aus
a*a+a*1+1*a+1*1
ein
a*a+2*a+1
oder ein
(a+1)*(a+1)
?
Hängt davon ab, was man damit machen will. Integrieren ist wohl mit der Summenform leichter und Nullstellenfinden mit der Produktform. Theoretisch müßtest Du beide "Vereinfachungen" ausprobieren und mit beiden Versionen bin zum Ende durchoptimieren und das beste Optimat dann nehmen. Und eine Summe wurde sich testhalber auch mal zur umgedrehnten SUmme "vereinfachen" (a+b)=>(b+a) und vielleicht schauen, ob linkes oder rechtes Kind auch Summe sind und mal rotieren (a+(b+c))=>((a+b)+c) und dann liegen die beiden PIs schon irgendwann beisammen. Uups, die Rechenzeit wäre enorm, besser so wenig wie möglich rumprobieren.Eine Summe mit mindestens einer Summe als Kind könnte sich auch "vereinfachen", indem sie die Kindessummanden alle hochzieht (a+(b+c))=>(a+b+c), den Parser stört es doch nicht, daß Summen auch mehr als 2 Summanden haben könnten, er erzeugt eben nur welche mit 2.
Also wegen des Optimierens würde ich den Parser nicht ändern. Zu überlegen wäre, ob Du aus anderen Gründen umsteigen magst.Hab das mal so gemacht:
class Node{//abstract … Node* optimize()=0;//Kann seine Kinder untersuchen und gerne umbauen. //gibt gewöhnlich this zurück. kann aber auch einen neuen //Node bauen, dann muss der Aufrufer halt den alten deleten und durch den //neuen ersetzen.
-
volkard schrieb:
Eine Summe mit mindestens einer Summe als Kind könnte sich auch "vereinfachen", indem sie die Kindessummanden alle hochzieht (a+(b+c))=>(a+b+c), den Parser stört es doch nicht, daß Summen auch mehr als 2 Summanden haben könnten, er erzeugt eben nur welche mit 2.
Also wegen des Optimierens würde ich den Parser nicht ändern. Zu überlegen wäre, ob Du aus anderen Gründen umsteigen magst.Hab das mal so gemacht:
class Node{//abstract … Node* optimize()=0;//Kann seine Kinder untersuchen und gerne umbauen. //gibt gewöhnlich this zurück. kann aber auch einen neuen //Node bauen, dann muss der Aufrufer halt den alten deleten und durch den //neuen ersetzen.Das hört sich für mich nach der nicht so effizienten Lösung an. Außerdem muss man das für jede Rechenart usw. einzeln schreiben. Den Parser umschreiben finde ich die schönere Lösung.
Vielen Dank
-
Was willste noch einbauen?
(0x)=0
(1x)=x
(0+x)=x
sqrt(x^x)=abs(x)
-
Schau dir vielleicht mal muParser an. Ich hab mir den Optimierer nicht genau angeschaut, ich hab nur gesehen, dass es einen gibt, der einige Fälle behandelt.
-
volkard schrieb:
sqrt(x^x)=abs(x)
Sicher, dass das so stimmt?
-
Ja, für x = 1 und x = 2
-
patrick246 schrieb:
volkard schrieb:
sqrt(x^x)=abs(x)
Sicher, dass das so stimmt?
sry.
x*x meinte ich.