Aufgaben

Hausaufgabe: Term darstellen und mit Stackmaschine auswerten

Geben Sie sowohl die Termbaumdarstellung als auch die Präfix- und Postfix-Darstellung des folgenden Ausdrucks an. Berücksichtigen Sie dabei implizite Präzedenzen wie in python.

2-1 > 0 and Math.sin(x) < 0.01

Wählen Sie dann eine geeignete Darstellung und werten Sie den Ausdruck für die Variablenbelegung x = 3.14 mit einer Stackmaschine aus.

Aufgabe: Stackmaschine programmieren

In dieser Aufgabe sollen Sie den Algorithmus zur Auswertung arithmetischer Ausdrücke in Postfix-Darstellung mit einer Stackmaschine in python implementieren.

Dazu ist es nützlich, dass die Stack-Operationen append¹ und pop für Listen in python definiert sind, wie die folgenden Beispielaufrufe zeigen:

>>> stack = []
>>> stack.append(42)
>>> stack
   [42]
>>> stack.append(43)
>>> stack
   [42,43]
>>> stack.pop()
   43
>>> stack
   [42]

Für eine definierte Liste stack (das auch anders heißen kann) ist also stack.append eine Prozedur, die sie Liste stack derart verändert, dass das übergebene Argument das neue letzte Element der Liste ist. Die Funktion stack.pop liefert das letzte Element von stack zurück und entfernt es aus der Liste stack.

Definieren Sie eine Funktion eval_postfix(expr), die einen Ausdruck in Postfix-Darstellung als Argument erwartet und das Ergebnis der Auswertung dieses Ausdrucks zurückliefert. Verwenden Sie intern eine Liste als Stack und manipulieren Sie diese entsprechend des Algorithmus aus der Vorlesung.

Der Ausdruck in Postfix-Darstellung kann ebenfalls als Liste dargestellt werden. Zum Beispiel kann der Ausdruck 1 1 + 1 - in python als Liste von Zahlen und Zeichenketten dargestellt werden, nämlich als [1, 1, '+', 1, '-'].

Zur Verarbeitung dieser Darstellung sind die folgenden vordefinierten Operationen hilfreich.

• Für einen beliebigen Python-Wert x liefert type(x)==str einen Wahrheitswert zurück, der angibt, ob es sich bei x um eine Zeichenkette handelt. Diese Operation können Sie verwenden, um Zahlen von Rechenoperationen im gegebenen Ausdruck zu unterscheiden.

• Für eine nicht-leere Liste a liefert a.pop(0) das erste Element zurück und entfernt es gleichzeitig aus a (pop(0) ist also wie pop(), aber nicht am Ende sondern am Anfang der Liste). Diese Operation können Sie verwenden, um das nächste Element aus dem Ausdruck herauszuholen.

Der Aufruf eval_postfix([1, 1, '+', 1, '-']) soll das Ergebnis 1 liefern. Gehen Sie davon aus, dass nur gültige Postfix-Darstellungen als Argument übergeben werden. Ihre Implementierung soll mindestens die im Beispiel verwendeten binären Operatoren + und - erlauben.