Termdarstellungen lassen sich am einfachsten mit rekursiven Definitionen erzeugen:
def infix(term):
if type(term)==list:
return "(" + infix(term[1]) + term[0] + infix(term[2]) + ")"
else:
return str(term)
def prefix(term):
if type(term)==list:
return [term[0]] + prefix(term[1]) + prefix(term[2])
else:
return [term]
def postfix(term):
if type(term)==list:
return postfix(term[1]) + postfix(term[2]) + [term[0]]
else:
return [term]
Im rekursiven Fall werden die Ergebnisse der beiden rekursiven Aufrufe jeweils an geeigneter Stelle mit dem Operationssymbol des Terms verknüpft.
Die Funktion eval_expr testet, ob das Argument eine Liste ist. Wenn nicht, ist der Ausdruck bereits vollständig ausgewertet (weil er z.B. eine Zahl ist) und kann unverändert zurückgegeben werden. Im Fall einer Liste setzen wir vorraus, dass das erste Element eine Rechenoperation mit genau zwei Argumenten ist, die als zweites und drittes Element in der Liste stehen. Wir berechnen mit rekursiven Aufrufen zunächst die Werte der Argument-Ausdrücke und übergeben diese dann an die Funktion eval_op, die die Rechenoperation auf die Argumente anwendet.
def eval_expr(expr):
if type(expr)==list:
return eval_op(expr[0], eval_expr(expr[1]), eval_expr(expr[2]))
else:
return expr
Die Funktion eval_op testet, welche Operation als erstes Argument übergeben wurde, verknüpft entsprechend das zweite Argument mit dem dritten und liefert das Ergebnis zurück.
def eval_op(op, x, y):
if op == "+":
return x + y
if op == "-":
return x - y
if op == "*":
return x * y
if op == "/":
return x / y
Mit diesen Definitionen liefert der obige Aufruf das Ergebnis 3.5.
Der Ausdruck 2-1 > 0 and Math.sin(x) < 0.01 entspricht dem folgenden Termbaum.
and
/ \
> <
/ \ / \
- 0 sin 0.01
/ \ |
2 1 x
Die Präfixdarstellung ist and > - 2 1 0 < sin x 0.01.
Die Postfixdarstellung ist 2 1 - 0 > x sin 0.01 < and.
Letztere eignet zur Auswertung mit einer Stackmaschine. Für x = 3.14 ergibt sich die folgende Auswertung.
Stack Ausdruck
------------------- ------------------------------
2 1 - 0 > 3.14 sin 0.01 < and
2 1 - 0 > 3.14 sin 0.01 < and
2 1 - 0 > 3.14 sin 0.01 < and
1 0 > 3.14 sin 0.01 < and
1 0 > 3.14 sin 0.01 < and
True 3.14 sin 0.01 < and
True 3.14 sin 0.01 < and
True 0.002 0.01 < and
True 0.002 0.01 < and
True True and
True
Das Ergebnis der Auswertung ist also True.
Die Funktion eval_postfix manipuliert in einer bedingten Schleife einen Stack, solange der gegebene Ausdruck noch Einträge enthält. In jedem Schleifendurchlauf wird dem Ausdruck ein Element entnommen. Zahlen werden aus dem Ausdruck auf den Stack geschoben. Wenn das nächste Element des Ausdrucks ein Operator (also eine Zeichenkette) ist, werden zwei Elemente vom Stack genommen und mit dem Operator verknüpft. Dabei müssen wir das zweite Argument zuerst vom Stack nehmen, da es diesem vorher als zweites hinzugefügt wurde (für die Addition spielt die Reihenfolge der Argumente keine Rolle, für die Subtraktion aber sehr wohl). Wenn das Argument ein gültiger Ausdruck in Postfix-Darstellung war, enthält der Stack nach Abarbeitung der Schleife genau ein Element, das wir als Ergebnis zurückliefern.
def eval_postfix(expr):
stack = []
while len(expr) > 0:
elem = expr.pop(0)
if type(elem)==str:
y = stack.pop()
x = stack.pop()
stack.append(eval_op(elem, x, y))
else:
stack.append(elem)
return stack.pop()
Diese Implementierung verwendet eine Hilfsfunktion evalOp, die eine binäre Operation und zwei Argumente übergeben bekommt und das Ergebnis der Anwendung der Operation auf die Argumente zurückliefert.
def eval_op(op, x, y):
if op == "+":
return (x+y)
if op == "-":
return (x-y)
Wir verwenden hier mehrere optionale return-Anweisungen (statt geschachtelter bedingter Verzweigungen) um anzudeuten, dass alle Operationen gleichberechtigt sind.