Einstieg - Auswertung von Rechenterme
Darstellung von Rechentermen
Rechenterme sind Ausdrücke wie z. B. (92 - 79) * 27
, die aus Zahlen, Rechenzeichen und
Klammern bestehen.
Es gibt eine Reihe von Möglickeiten, solche Rechenterme mit Hilfe von Datenstrukturen darzustellen:
- als Zeichenkette
'(92 - 79) * 27'
- als Liste von Zahlen und Zeichen
['(', 92, '-', 79, ')', '*', 27]
- als verschachtelte Liste von Zahlen und Rechenzeichen
['*', ['-', 92, 79], 27]
- als Liste von Zahlen und Rechenzeichen
['*', '-', 92, 79, 27]
- ...
Alle diese Darstellungen haben ihre Vor- und Nachteile. Für welche man sich entscheidet, hängt u. a. davon ab, wie die Verarbeitung der Rechenterme erfolgen soll.
Wir werden im Folgenden die letzte Darstellung benutzen. Dieser Darstellung liegt die
Operatorsicht zu Grunde: Der Term (92 - 79) * 27
lässt sich in Operatornotation in der
Form *(-(92, 79), 27)
darstellen. Aus dieser Darstellung gewinnt man direkt die
Listennotation ['*', '-', 92, 79, 27]
.
Warum diese Notationen Vorteile bei der automatisierten Verarbeitung haben, wird unten gezeigt.
Aufgabe 1
Wandle die folgenden Rechenterme in Listennotation um:
85 - (79 - 43)
(85 + 34) * (28 - 17)
85 * ((79 - 23) - 43)
Auswertung von Rechentermen
Die folgende Abbildung zeigt ein Verfahren, wie man Rechenterme auswerten kann. Man benutzt hierzu zwei Stapel, die schrittweise abgearbeitet werden.
Aufgabe 2
Analysiere und beschreibe das gezeigte Verfahren. Berechne analog den Wert von einem der Terme aus Aufgabe 1.
Aufgabe 3
Entwickle einen Algorithmus, der das gezeigte Verfahren präzise beschreibt.