55. Bäume III: Rechnen

Jetzt wollen wir einen Baum aus einem mathematischen Ausdruck bauen. Dazu leiten wir aus unserem Ur-Baum einen Baum ab, der die Ausdrücke gleich aus einer tokenisierten Präfix-Notation herausparst:

class ExpressionTree(BinaryTree):
  def __init__(self, tokens):
    try:
      val = float(tokens[0])
    except ValueError:
      val = tokens[0]
    del tokens[0]
    BinaryTree.__init__(self, val)
    if not self.isLeaf():
      self.setLeft(self.__class__(tokens))
      self.setRight(self.__class__(tokens))

   def isLeaf(self):
    """returns true if the node is the leaf of an expression tree.
    """
    return type(self.value)==type(1.0)

In der Präfix-Notation kommt der Operator vor den Operanden (die übliche mathematische Notation heißt Infix-Notation). Aus c× (a+ b) wird auf diese Weise * c + a b. Der Vorteil ist, dass es sehr leicht ist, aus dieser Notation einen Baum zu bauen, nicht nur, weil man sich nicht um Präzedenz kümmern muss und auch Klammern verzichtbar sind. Sprachen wie Lisp verwenden diese Art von Notation, die übrigens eng verwandt ist mit der Art, wie wir Funktionen aufrufen (mul(c, add(a, b))), während Forth oder Postscript eine Postfix-Notation benutzen; da heißt es dann c a b + *. Taschenrechner von HP werden so ähnlich bedient, und wer sich einmal dran gewöhnt hat, will andere Taschenrechner gar nicht mehr anfassen.

Der Konstruktor erwartet eine Liste von Tokens. Dabei versteht man unter Tokenizing oder auch lexikalischer Analyse die Umwandlung eines Strings in einzelne Tokens. Ein Token wiederum ist ein “Atom” der Sprache, die man nachher parsen möchte, also eine unteilbare Einheit, deren innere Struktur irrelevant für den Parser ist. Ein Parser für Ausdrücke interessiert sich nicht dafür, dass 3.1415 vielleicht durch einen String der Länge Sechs repräsentiert wird oder durch 80 Bits. Was ihn interessiert, ist dass hier ein Float-Literal steht.

Um den Baum aus so einer Präfix-Notation herauszuparsen, gehen wir wie folgt vor:

Wenn noch Eingabetoken vorhanden sind

Erzeuge einen Knoten aus dem nächsten Eingabetoken und lösche es

sonst

Löse einen Fehler aus

Wenn der Knoten einen Operator enthält:

Parse einen Baum aus der Eingabe und hänge ihn links ein Parse einen Baum aus der Eingabe und hänge ihn rechts ein

Gib den Knoten zurück

Die Entscheidung, ob ein Knoten einen Operator enthält oder nicht, ist einfach die Entscheidung, ob wir es mit einem inneren Knoten oder einem Blatt zu tun haben, denn unsere Grammatik sagt, dass literale Zahlen Blätter sind. Deshalb konditionieren wir den rekursiven Aufruf auf isLeaf, das seinerseits einfach nachsieht, ob unser Wert ein Float ist oder nicht.

Um jetzt den Wert des Ausdrucks zu finden, machen wir eine implizite Inorder-Traversierung wie etwa in folgender Methode:

  def compute(self):
    if self.isLeaf():
      return float(self.getValue())
    else:
      return eval("%f%s%f"%(
        self.left.compute(),
        self.getValue(),
        self.right.compute()))

Probieren wirs mal aus:

>>> import tree
>>> et = tree.ExpressionTree(
  "/ 8 + 3 * 4 7".split())
>>> print et
/
        8.0
        +
                3.0
                *
                        4.0
                        7.0
>>> et.compute()
0.25806451612903225
>>> 8./(3+4.*7.)
0.25806451612903225

Wir scheinen also richtig zu rechnen.