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 Arrays 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 ein definiertes Array stack (das auch anders heißen kann) ist also stack.append eine Prozedur, die das Array stack derart verändert, dass das übergebene Argument das neue letzte Element des Arrays ist. Die Funktion stack.pop liefert das letzte Element von stack zurück und entfernt es aus dem Array 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 ein Array als Stack und manipulieren Sie es entsprechend des Algorithmus aus der Vorlesung.

Der Ausdruck in Postfix-Darstellung kann ebenfalls als Array dargestellt werden. Zum Beispiel kann der Ausdruck 1 1 + 1 - in python als Array 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 ein nicht-leeres Array 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 des Arrays). 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.