Funktionsinterpreter
Die Theorie
Der eine oder andere mag vielleicht einmal auf das Problem gestoßen sein, dass man es dem Benutzer seines Programms ermöglichen möchte, eine mathematische Funktion oder einen Term einzugeben, der dann zur Laufzeit ausgewertet wird. Wie man einen einfachen Funktionsinterpreter zu genau diesem Zweck schreibt, wird in diesem Tutorial beschrieben.
Grundsätzlich gibt es drei verschiedene Arten, einen Term aufzuschreiben: die Infix-, die Präfix sowie die Postnotation. Die Infixnotation ist die uns bekannte, relativ intuitive Schreibweise eines Terms, bei der der Operator zwischen die Operatoren geschrieben wird. Bei der Präfixnotation (auch häufig als polnische Notation bezeichnet) wird der Operator vor die Operanden geschrieben, während bei der Postfixnotation (auch häufiger als umgekehrte polnische Notation zu finden) der Operator hinter die Operanden geschrieben wird.
Bei der Infixnotation wird der Operator auf die links und rechts stehenden Operanden angewendet. Dabei ist natürlich die Punkt- der Strichrechnung vorzuziehen. Aus z.B. dem Term 5 * 8 + 7 wird dann zunächst 40 + 7 und dies wird vereinfacht zu 47.
Bei der Präfixnotation wirkt der Operator auf die nächsten zwei rechts stehenden Operanden. Dabei ist lediglich die Reihenfolge wichtig – die Regel Punkt vor Strich gilt hier nicht. Unser Term sieht also hier folgendermaßen aus: + * 5 8 7.
Da bei + * 5 8 7 rechts vom Plus ebenfalls ein Operator steht, muss dieser vorgezogen werden. Es wird also zunächst zu + 40 7 vereinfacht, so dass der Plus-Operator angewendet werden kann und der Term zu 47 wird.
Ähnlich funktioniert die Postnotation. Die Operatoren wirken auf die beiden links vom Operator stehenden Operanden. Punkt vor Strich gilt auch hier nicht. Unser Beispielterm wandelt sich also zu 5 8 * 7 +.
Der Term 5 8 * 7 + wird zunächst zu 40 7 + vereinfacht, da die Multiplikation von links gesehen der erste Operator ist, und anschließend zu 47, da die Addition hier auf die 40 und 7 angewendet werden muss.
Der Funktionsinterpreter, den wir im Folgenden entwickeln werden, wird die umgekehrte polnische Notation (UPN) nutzen. Nun könnte man sich fragen, warum? Wo sich die Infixnotation doch so viel bequemer anwenden lässt. Die Antwort darauf ist die Implementierung. Bei der Infixnotation müssen so z.B. Klammern oder bestimmte Rechenregeln (Punkt vor Strich) beachtet werden – bei der UPN hingegen nicht. Außerdem erlaubt uns diese Notation, wie wir noch sehen werden, eine wesentlich angenehmere Weise, den Interpreter dann tatsächlich zu implementieren. Wenn wir wollen, können wir natürlich die sogenannte Infixnotation, welche den meisten gängiger sein dürfte, später auch noch in Postfixnotation umwandeln.
Ehe wir uns aber an die Grundidee machen, fehlt uns zunächst noch ein kleines Hilfsmittel.