Mathebaum (Binärbaum) vereinfachen

[Alaitoc]

Tach zusammen,
mein Matheparser ist größtenteils vollständig. Ich würde jetzt meinen Binärbaum (siehe Bild), das zum Beispiel aus:

1*x = x
x+x = 2x
x*x =x^2
a*b+a*c=a*(b+c)

etc...

Jedoch weiß ich ehrlich gesagt nicht genau wie ich das umsetzten soll, die Codestruktur meines Baumes sieht so aus:

type PTBinaryNode = ^TBinaryNode;
TBinaryNode = record
Token:TToken;
UpNodeTBinaryNode;
RightNodeTBinaryNode;
LeftNodeTBinaryNode;
end;

Dabei besteht TToken aus:

type
TTokens = (tkUnknown,
tkInteger,tkFloat,tkVar,
tkAdd,tkSub,tkDiv,tkMul,
tkBrOpen,tkBrClose,tkPotenz);

type TToken = class(TObject)
Token: TTokens;
Value: String;
end;

Habt ihr vielleicht eine Idee wie ich das lösen könnte?

MfG Alaitoc

[Alaitoc]

Falls was unklar ist oder ihr mehr Informationen benötigt, bitte fragen.

MfG Alaitoc

[jfheins]

Ich weis jetzt nicht so genau, was du machen willst ...

Willst du aus dem String dem Baum machen? Dafür brauchst du einen Parser. Andererseits schriebst du, du hättest genau diesen schon fast fertig ..

Beachte übirgens, dass es auch (wenige) unäre Operatoren gibt. Z.B. das minus vor einer Zahl oder ein ²

Möchtest du auch noch Funktionen einbauen?

[Corpsman]

ich mus gestehen ich versteh auch nicht genau was deine Frage ist.

aber wenns dir darum geht an zu sehen wie ein Parser geht da habe ich Hier was für dich.

[Alaitoc]

Also ich habe meinen Parser soweit fertig, d.h. :

• Screener (entfernen der Leerzeichen etc...)
• Lexikalischer Scanner
• Parser (erstellt einen Parsebaum (Binärbaum)
• Berechnung des Parsebaums (+,-,*,/,x^y)
• Variablen können durch Werte ersetzt werden

Nun will ich das der Parsebaum sich soweit zusammenfasst wie es geht, also würde im Baum z.b.

3*x+4*x

Würde daraus:

7*x

Sozusagen Vereinfachen von Termen in der Mathematik auf meinen Parsebaum (siehe Bild) angewandt.

Dabei besteht mein Parsebaum halt wie bei einer verketteten Liste aus nem Wert und einem Zeiger aufs nächste Objekt (bei meinem Baum wären das aber dann 2 Zeiger pro Wert).

Ich bräuchte nun einen Ansatz dafür wie ich das Vereinfachen des Baumes umsetzten kann.

Edith: Das man sozusagen auch Variablen addieren kann in meinem Parser: x+x = 2x und so weiter...

MfG Alaitoc

[Corpsman]

Also ich höre gerade ne Vorlesung "Programmanalysen und Compilerbau" und in der wird sowas gemacht.

Ich empfehle dir nu einfach mal das Drachenbuch generell kann ich dir zu dem Thema aber schon gleich sagen das es Aufwendig wird wenn du es richtig machen willst, sonst wirds ne "Hack" Lösung.

Must dich entscheiden was genau du willst.

[jfheins]

Wenn ich dir richtig verstanden habe, möchtest du sowas: http://reference.wolfram.com/mathema.../Simplify.html

Du möchtest also das tun, weshalb ich Mathematica so gerne mag

Um dir eine Idee zu geben: Du brauchst auf jeden Fall eine Funktion, die soviel faktorisiert, wie möglich und eine die soviel ausmultipliziert, wie möglich. Ggf. noch andere, komplexere Funktionen, aber das sind die beiden ersten.

Wie man die jetzt genau realisiert, bin ich aber überfragt ... jetzt bräuchte man einen Informatiker

[Khabarakh]

Das ist symbolisches Rechnen, nicht gerade ein einfaches Thema. Solange man aber kein Mathematica-Niveau anstrebt, dürften die einfacheren Regeln noch machbar sein.

Mal ein paar Gedanken zum Zusammenfassen zum Vereinfachen von Summen: Ich würde als kleinste Einheit ein Monom, also ein Produkt mit Koeffizient und einem Set von Variablen (inkl. Hochzahl), betrachten, also z.B. "3xy²", was dann also Objekt so etwa dargestellt werden könnte:

Code:

{ Coefficient = 3; Variables = { { Name = "x"; Exponent = 1 }; { Name = "y"; Exponent = 2 } } }

Bei einer Summe kannst du dann nach Summanden mit gleicher Variablen-Menge suchen und sie durch Addition der Koeffizienten zusammenfassen.

[Alaitoc]

Ah das hört sich doch soweit schonmal gut an :>

Schonmal danke, werde dann mal schauen wie ich das genau mit dem symbolischem Rechnen in mein Programm einbaue.

MfG Alaitoc