Logo Mathematik · Physik · Informatik
Arnold-Janssen-Gymnasium St.Wendel
Universität des Saarlandes · Fachrichtung Mathematik

Kontakt · Impressum

Lazarus IDE Quelltext

Ein mathematischer Parser in Delphi

Was ist ein mathematischer Parser?

In seiner einfachsten Form ist ein mathematischer Parser ein Programm, das einen mathematischen Term (bestehend aus Zahlzeichen, Rechenzeichen und Klammern) auswertet. An Beispielen erklärt: Die Zeichenkette "3+5" wird vom Parser verarbeitet zu 8, und aus "9*(8+4*4)/(7-4)" wird 72.

Wie funktioniert ein mathematischer Parser?

Das zweite Beispiel zeigt, wo die Schwierigkeit steckt: Rechenausdrücke beliebiger Länge, die evtl. durch Klammern gegliedert sind, sollen gemäß der mathematischen Vorrangregeln (Klammern vor Potenz vor Punkt vor Strich) abgearbeitet werden. Das kann am einfachsten durch Rekursion erreicht werden: Wir schreiben eine Funktion
 function evaluate(term: string): string; 
die einen Term an den Operatoren (+,-,*,/,^) und Klammern in Teilterme zerlegt und sich dann selbst wieder aufruft mit den einzelnen Teilen als Argument. Auch hier ein Beispiel (zwar etwas schlampig notiert, aber das Prinzip wird deutlich):
 evaluate ('3+4*5') = evaluate('3') + evaluate('4*5')
                    =       3       + evaluate('4') * evaluate('5')
                    =       3       +       4       *       5
Also: Enthält das Argument von evaluate kein Rechenzeichen mehr, wird es selbst zurückgeliefert. Ansonsten wird das Argument zerlegt, zunächst am letzten (d.h. am weitesten rechts) stehenden + oder -. Falls ein solches nicht vorhanden ist, am letzten auftretenden * oder /. Dadurch wird Punkt- vor Strichrechnung gewährleistet (siehe Bsp. oben).

Um Klammern richtig zu behandeln, muss man lediglich nach den Operatoren + und - bzw. * und / nur außerhalb aller Klammern (ansonsten wie oben beschrieben) suchen lassen, und ganz außen stehende Klammern entfernen lassen, d.h. am Beispiel:
 evaluate ('(3+4)') = evaluate('3+4').
Das genügt bereits, um alle in Mathe definierten Vorrangregeln korrekt abzubilden.

Vier Hilfsfunktionen

Unten ist der Quelltext der Funktion evaluate als Kopiervorlage angegeben. Benötigt werden allerdings noch vier Hilfsfunktionen: Zunächst
  function global_bracket(term: string) : boolean;
die entscheidet, ob ein Term von einer äußeren Klammer umgeben ist, also die Form "(....)" hat; dann die Funktionen zum Auffinden des jeweils letzten vorkommens der Rechenzeichen außerhalb von Klammern, und zwar
  function find_last_add(term: string) : integer;
für das letzte Vorkommen eines + oder - Zeichens,
  function find_last_mul(term: string) : integer;
für das letzte Vorkommen eines * oder / Zeichen sowie
  function find_last_power(term: string) : integer;
für das letzte Vorkommen eines Hochzeichens ^. Rückgabewert ist die letzte Position des betreffenden Zeichens innerhalb von term, bzw. 0, falls das Zeichen nicht vorkommt.

Der Quelltext des eigentlichen Parsers

Die nachfolgend angegebene Funktion evaluate realisiert den eigentlichen Parser. Man beachte, dass der Rückgabewert von evaluate selbst wieder vom Typ string ist. Syntaxfehler im Term führen in der Regel dazu, dass evaluate keine gültige Zahldarstellung zurückliefert, also kann eine Einbindung mit rudimentärem Fehlertest wie folgt aussehen:
 try
   value := evaluate(term);
   numerical_value := StrToFloat(evaluate);
 except value := 'error';
Hier also nun endlich der Quelltext:

function evaluate(t : string): string;

var       pos: integer;
           op: string;
     left_arg: string;
    right_arg: string;

begin

   // Schritt 1: Entferne (falls vorhanden) eine einschließende
   //            globale Klammer,  z.B. aus (8+4-5) wird 8+4-5
   // -----------------------------------------------------------

   if global_bracket(t) = true then
        t := evaluate(AnsiMidStr(t,2,length(t)-2));

   // Schritt 2: Werte den letzten Additionsoperator
   //            außerhalb von Klammern aus.
   // -----------------------------------------------------------

   pos := find_last_add(t);

   if pos > 0 then begin
       // ermittle den Operator sowie die beiden Argumente
       op := ansimidstr(t,pos,1);
       if pos = 1 then  // Sonderfall: +/- als Vorzeichen!
            left_arg := '0'  // setze left_arg = 0
       else left_arg := evaluate(ansileftstr(t, pos-1));
       right_arg := evaluate(ansirightstr(t, length(t)-pos));

       // führe die Rechnung durch (Fallunterscheidung nach Operator)
       if op = '+' then
          result :=
             FloatToStr(StrToFloat(left_arg) + StrToFloat(right_arg))
       else
          result :=
             FloatToStr(StrToFloat(left_arg) - StrToFloat(right_arg));
       exit;
   end;

   // Schritt 3: Werte den letzten Multiplikationsoperator
   //            außerhalb von Klammern aus.
   // -----------------------------------------------------------

   pos := find_last_mul(t);

   if pos > 0 then begin
       op        := ansimidstr(t,pos,1);
       left_arg  := evaluate(ansileftstr(t, pos-1));
       right_arg := evaluate(ansirightstr(t, length(t)-pos));

       if op = '*' then
          result :=
            FloatToStr(StrToFloat(left_arg) * StrToFloat(right_arg))
       else
          result :=
            FloatToStr(StrToFloat(left_arg) / StrToFloat(right_arg));
       exit;
   end;

   // Schritt 4: Werte den letzten Multiplikationsoperator
   //            außerhalb von Klammern aus.
   // -----------------------------------------------------------

   pos := find_last_power(t);

   if pos > 0 then begin
       left_arg  := evaluate(ansileftstr(t, pos-1));
       right_arg := evaluate(ansirightstr(t, length(t)-pos));

       result :=
         FloatToStr(Power(StrToFloat(left_arg),StrToFloat(right_arg)));
       exit;
   end;

   // Falls nicht weiter vereinfachbar: Liefere Term selbst wieder zurück.
   // --------------------------------------------------------------------

   result := t;

 end;

Download

Parser Delphi-Quelltext (erstellt mit Lazarus IDE v0.9.30.4)

Valid XHTML 1.0 Transitional letzte Aktualisierung: 04.08.2013