Funktionsinterpreter
Interpreter Nr. 1
Nun beginnen wir mit der eigentlichen Arbeit an unserem Interpreter.
Die Idee ist also wie folgt:
- Wir zerlegen den Eingabestring in die einzelnen Symbole.
- Wir gehen die Eingabesymbole von links nach rechts durch und unterscheiden dabei drei Fälle:
- Es handelt sich um eine Zahl. Dann landet diese umgehend auf dem Stack.
- Es handelt sich um das Symbol ‚x‘. Dann landet der Wert von x direkt auf dem Stack.
- Es handelt sich um einen Operator. Je nach dem, um was für einen Operator es sich handelt, holen wir einen oder zwei Operanden vom Stack, wenden den Operator darauf an und bringen das Ergebnis wieder auf den Stack.
- Wenn wir alle Symbole abgearbeitet haben, brauchen wir nur noch das letzte Objekt auf dem Stack zurück zu liefern.
Wir benötigen also zunächst eine Methode, welche den Eingabestring auftrennt. Als Trennungszeichen wird hier das Leerzeichen verwendet.
procedure SplitString(res: TStringList; str: String; seperator: Char); var Pos: Integer; begin repeat Pos := AnsiPos(seperator, str); if Pos <> 0 then begin res.Add(Copy(str, 0, Pos - 1)); str := Copy(str, Pos + 1, Length(str)); end else res.Add(str); until (Pos = 0); end;
Die eigentliche Prozedur zum Interpretieren der (mathematischen) Funktion ist nun die Umsetzung der oben beschriebenen Regeln. Lediglich die eigentlichen Zuweisungen sind durch den Umweg über TNumber etwas ungewohnt. Zudem müssen wir daran denken, die nicht mehr benötigten Instanzen jedes mal wieder frei zu geben, da ansonsten unnötig viel Speicher reserviert wird.
function interpret(const func: String; x: Extended): Extended; var splittedFunction: TStringList; i: Integer; Stack: TStack; isNumber: Boolean; val: Extended; a, b: TNumber; begin // Splitte den String in die einzelnen Symbole splittedFunction := TStringList.Create(); SplitString(splittedFunction, func, ' '); // Stack bereit machen Stack := TStack.Create(); // Jedes Symbol abarbeiten for i := 0 to splittedFunction.Count - 1 do begin // 1. Fall: Es handelt sich um das x. if splittedFunction[i] = 'x' then begin // Bring das x auf den Stack stack.Push(TNumber.Create(x)); end else begin // 2. Fall: Handelt es sich um eine Zahl? isNumber := TryStrToFloat(splittedFunction[i], val); if isNumber then begin // Bring die Zahl auf den Stack stack.Push(TNumber.Create(val)); end // Es handelt sich um einen Operator. Finde nun raus, welcher das ist else if splittedFunction[i] = '+' then begin a := stack.Pop(); b := Stack.Pop(); a.setNumber(a.getNumber() + b.getNumber()); b.Free(); stack.Push(a); end else if splittedFunction[i] = '-' then begin a := stack.Pop(); b := Stack.Pop(); a.setNumber(b.getNumber() - a.getNumber()); b.Free(); stack.Push(a); end else if splittedFunction[i] = '*' then begin a := stack.Pop(); b := Stack.Pop(); a.setNumber(a.getNumber() * b.getNumber()); b.Free(); stack.Push(a); end else if splittedFunction[i] = 'sqrt' then begin a := stack.Pop(); a.setNumber(sqrt(a.getNumber())); stack.Push(a); end; end; end; // Liefere das Ergebnis zurück a := stack.pop(); result := a.getNumber(); // Gebe noch alle Ressourcen frei splittedFunction.Free(); a.Free(); end;
Etwas ist jetzt auffällig. In dem Ausschnitt
if splitted_function[i] = '-' then begin a := stack.Pop(); b := Stack.Pop(); a.setNumber(b.getNumber() - a.getNumber()); stack.Push(a); end;
werden die Operanden vertauscht. Die Frage nach dem Warum kann man sich damit erklären, dass der Stack die Werte genau verkehrt herum bereitliegen hat. In der UPN wird der Ausdruck 5 – 2 etwa zu 5 2 -. Damit landet zunächst die 5 und dann erst die 2 auf dem Stack. Werden diese nun der Reihenfolge nach abgerufen, so erhalten wir zunächst die 2 und dann die 5. Um dies zu korrigieren, müssen wir also bei sämtlichen Verknüpfungen, die nicht kommutativ sind, die Operanden vertauschen.
Wir sind soweit fertig und haben damit einen einfachen Funktionsinterpreter geschrieben. Da etwa bei der Berechnung von 200.000 Werten der Funktion f: x -> (x^2 + 2)^(1/2) viele Schritte unnötigerweise mehrfach ausgeführt werden, werden wir uns im nächsten Abschnitt anschauen, wie wir derartige Berechnungen noch beschleunigen können.