Mathematische Formeln parsen

[Coder1990]

Hallo,

ich habe mir vorgenommen meine Facharbeit im Bereich Mathematik-Informatik zu schreiben und habe mich nun dazu entschieden einen Formel Parser zu erstellen. Nun bräuchte ich vll ein paar Tipps wie ich da am besten vorgehen sollte.

Meine momentane Überlegung sieht folgendermaßen aus:
Jede neu eingespeicherte Funktion wird in einer Klasse TFunction abgespeichert, die über benutzte Variablen bescheid weiß und wie die Funktion als String aussieht. Darüber hinaus besitzt die Klasse TFunction nun einen TBlock der wiederum aus mehreren TBlöcken besteht welche die einzelnen Rechenoperationen in sozusagen in Blöcke fassen.
Bsp: (die {} Klammern symbolisieren Blöcke
2x^2 - x^3 + x(x-2)
-> {{2x^2} - {x^3} + {x(x-2}}
-> {{2}*{{x}*{x}}} - {{x}*{x}*{x}} + {{x}*{{x}-{2}}}

Nun genauer am 1. Rechenblock:
1. Stufe {{2}*{{x}*{x}}}
2. Stufe {2}*{{x}*{x}}
3. Stufe {2} // {{x}*{x}} (das '*' muss sepearat in der 2. Stufe gespeichert werden!)
4. Stufe - // {x} * {x}
5. Stufe - // {x} // {x} ('*' in Stufe 4 abgespeichert)

Wenn ich nun für x einen Wert einsetzen will wird rekursiv sozusagen von unten nach oben alles durchgerechnet.

Leider bin ich in Sachen Rekursion nicht sonderlich begabt und bin mir nicht sicher wie ich das am Besten lösen soll.

Meine momentanen Klassen sehen so aus:

Delphi-Quellcode:

  TBlock = class
  private
  FInnerBlocks:array of PBlock;
  FCalcMethod: array of TCalcMethod;
  FSource: PFunction;
  FNegative: boolean;
  // function Calculate:real;
  public

  // property Result: real read Calculate;
  function AddBlock(s:string):integer;
  procedure AddCalc(a:char);
  property Negative: boolean read FNegative write FNegative;
  property Source : PFunction read FSource write FSource;
  constructor Create;
  function Read(f:string):integer;
  end;


  TFunction = class
  private
  FSourceFunction:string;
  FFunction: PBlock;
  FVars: TStringlist;

  public


  procedure ShowVars(l:TListbox);
  constructor Create(f:string);
  end;

Die rekursive Funktion im TBlock ist "Read" und der Rückgabewert soll das Ende des momentan untersuchen Blocks im String ausgeben, also die Stelle im String wo der von der momentanen Read Funktion untersuche Block aufhört damit die aufrufende Read Funktion weitermachen kann.

Leider komme ich mit "Read" auf keinen grünen Zweig.

MfG

[jfheins]

Okay ... also Rekursion ist schon mal einen Schritt zu weit gedahct, würde ich fast sagen ...

Du solltest dir erstmal klar machen, was du genau machen musst. Die Implementation ist erst danach dran.

Im allgemeinen musst du einen Binären Baum aufbauen, der aus sog. Token besteht.

Das ist der kleinste Teil einer mathem. Formel (also so ähnlich, wie dein Block)

Das sieht dann im Endeffekt so aus, dass ein Knoten einen Operanden darstellt, und dieser dann 2 Kinder haben kann. Jedes Kind kann entweder ein weiterer Operand sein, oder ein Symbol (X, Y, 42 oder -1)
(Zumindest bei binären Operatoren wie plus und minus usw.)

D.h. 2x^2 - x^3 + x(x-2)

Wird zu einem Baum:

Code:

*             {-}
      {*}            {+}
  {^}    {2}     {^}        {*}
{X} {2}        {X} {3}   {X}   {-}
                             {X} {2}

Den kannst du dann berechnen (rekursiv oder iterativ) bzw. vorher x einsetzen.

Aber es gibt hier auch schon ein paar Mathe-Parser, da kannst du dir ja mal einen angucken ;)

Edit: Das parsen als Baum hat den Vorteil, dass du nachher schneller Rechnen kannst, als wenn du jedes mal den String parst, wenn du einen neuen X-Wert auswerten willst.
Außerdem kannst du das dann "kompilieren", um es noch schneller zu machen, aber das ist dann schon fortgeschritten ;)

[Coder1990]

Danke!

Also nachdem ich mir deine "Lösung" durchgelesen habe, bin ich zu dem Schluss gekommen, dass ich bei meiner Überlegung wohl ein bisschen zu kurz gedacht habe. Meine Methode wäre halb rekursiv halb Schleifenabhängig und damit unglaublich kompliziert geworden.

Ich habe nun in den letzten Tagen versucht diesen binären Baum umzusetzen und es klappt sogar (auch wenn ich noch ein paar kleine Fehler fixen muss wie z.b. dass die "()" - Benutzung zu Problemen führt)!!
Ich nehme aber an, dass ich diese Probleme in den nächsten paar Tagen in den Griff bekomme!

Da mein Projekt auf eine komplette Kurvendiskussion hinauslaufen soll graut es mir schon vor den Nullstellen Berechnungen sowie Nullsetzungen anderer Terme. Nun wollte ich mal im vorab schon fragen wie man das am Besten macht:
Muss man die Gleichung irgendwie 0 setzen und auflösen oder setzt man unendlich viele Werte ein (wohl eher nicht^^) oder gibt es da eine andere schlauerere Methode?

MfG

[jfheins]

Zu den Nullstellen: schau dir mal das Newton-Verfahren an ;)

Kurz: Tangente an Punkt a_0 bilden, Nullstele suchen, an f(Nullstelle) Tangente bilden usw. Bis du hinreichend genau dran bist ;)

[Hador]

Hi Coder1990,
am Freitag gab es schon einen Thread zu diesem Thema. Dort habe ich schonmal folgendes zur Vorgangsweise geschrieben:

Zitat:

Zitat von Hador

- Operatorenreihenfolge feslgegen
- Operator mit der höchsten Priorität in dem String suchen
- Als Wurzel in einen Baum einfügen
- Reststrings (je nach parameteranzahl des Operators/der Funktion) als Child-Knoten eingefügt
- das ganze für die Kinder und alle anderen Operatoren wiederholen
- Nachdem alles aufgeteilt wurde in der untersten Ebene anfangen zu berechnen

Mit einem Binärbaum kommt man leider nicht ganz so weit, da es mathematische Operationen nicht nur mit zwei Variablen gibt.

Übrigends ist Rekursion garnicht so schlacht - wenn auch in Zusammenhang mit einem Baum: Du kannst, nachdem du eine Wurzel gefunden hast, einfach die restlichen Teilstrings wiederum mit der selben Funtion aufrufen und somit weiter zerteilen, bis du den ganzen Ausdruck in deinem Baum untergebracht hast.

[alzaimar]

De Backus-Naur-Form der Grammatik für einen mathematischen Ausdruck enthält eine mögliche Lösung für die Implementierung eines Formelparsers. Schau mal nach 'BNF' oder 'Backus-Naur'. Eine andere Möglichkeit wäre eine Stackmaschine. Du überlegst Dir für jedes Token (Klammer-auf, Klammer-zu, +,-,*,/, Nummern etc.) was mit dem Stack passieren soll.