Prof. Dr. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 04.05.2006
Norbert Heidenbluth Blatt 2


Uni Logo



Allgemeine Informatik II (SS 2006)
für
(Wirtschafts-)Mathematiker/Physiker und E-Techniker



Abgabetermin: 11. Mai 2006

Nachdem wir im ersten Übungsblatt den Datentyp ``Stack'' kennengelernt haben, folgen in dieser Woche Aufgaben zu dessen Verwendung, d.h. daß beide Aufgaben dieses Blattes unter Verwendung eines Stacks gelöst werden sollen. Darüberhinaus beinhaltet Aufgabe 5 nochmals das Interface-Konzept, und in Aufgabe 6 steht nochmals der algorithmische Teil im Vordergrund.

Reverse Polish Notation (RPN) - 15 Punkte

Im Elektro-Fachmarkt Ihres Vertrauens erregte unter all den Taschenrechnern dieses Modell Ihre besondere Aufmerksamkeit. Bei genauerer Betrachtung seiner technischen Daten fiel Ihnen auf, daß er die RPN beherrscht, also die ``Reverse Polish Notation''.

Zwar behaupten in diesem Elektro-Markt alle, nicht blöd zu sein, aber eine Erklärung, was es mit der RPN auf sich hat, blieb man Ihnen dort schuldig.

Also: Die umgekehrte polnische Notation wurde 1920 von Jan Lukasiewicz erfunden, um mathematische Ausdrücke ohne Vorrangregeln (Klammern) schreiben zu können. Einerseits erleichtert das die Eingabe in Taschenrechner bzw. Computer, andererseits bekommt man beim Ausrechnen des eingegebenen Ausdrucks ``automatisch'' Zwischenergebnisse geliefert und kann so überprüfen, ob die Berechnung fehlerfrei abläuft.

Wie sieht aber nun diese Notation aus? Ganz einfach: der zu berechnende Ausdruck wird so umgestellt, daß jeweils jeder Operator seinem/seinen Operanden folgt. Statt 1 + 2 (gewöhnliche Notation) heißt es in RPN: 1 2 +. Auf diese Art werden auch komplexere Ausdrücke geschrieben: ((1+2)*3)! wird zu 1 2 + 3 * !, und (1+2*3)! wird zu 1 2 3 * + !. Man sieht, daß also keine Klammern mehr benötigt werden.

Begriffe:

Unsere gewohnte Notation wird im Sprachgebrauch als Infix-Notation bezeichnet, die RPN nennt man hingegen Postfix-Notation.

Aufgabe 5: Ein RPN-Rechner (6 Punkte)

Ein Rechner, der nach der RPN arbeitet, kann zum Beispiel unter Verwendung eines Stacks wie folgt implementiert werden:

Der eingegebene Ausdruck wird einerseits dahingegen gerprüft, daß er nur erlaubte Zeichen enthält, und gleichzeitig wird dabei wie folgt zwischen Operanden und Operatoren unterschieden:

Und damit sind wir bereits bei der folgenden Aufgabe:

Schreiben Sie ein Java-Programm, das (nacheinander) beliebig viele Eingabezeilen in der RPN einliest, auswertet/berechnet und am Ende jeder Eingabezeile den Inhalt des Stacks ausgibt.

Ihr Programm soll dabei die folgenden Anforderungen erfüllen:

Beispiel:

   theseus$ java PostfixCalc
   Calculator> 12 11 2 * 6 2 / - +
   31
   Calculator> 12 11 2 6 - * + 2 /
   -16
   Calculator> 12 +
   Stack underflow!
   12

Aufgabe 6: Infix $\rightarrow$ Postfix (9 Punkte)

Natürlich möchten Sie Ihren Rechner aus Aufgabe 5 umfangreich testen, andererseits ist für Sie die RPN ja doch irgendwie ungewohnt. Da wäre es doch schön, einen Konverter zu haben, gell? Und schon sind wir bei der nächsten Aufgabe:

Schreiben Sie ein Java-Programm, das einen Ausdruck in Infix-Notation einliest und in Postfix-Notation umgewandelt wieder ausgibt.

Den folgenden Anforderungen sollte dieser Konverter genügen:

Beispiel:

   theseus$ java InfixToPostfix
   Infix: 12 + 11 * 2 - 6 / 2
   Postfix: 12 11 2 * 6 2 / - +
   Infix: (12 + 11 * (2 - 6)) / 2
   Postfix: 12 11 2 6 - * + 2 /

Tips zum Vorgehen:

Viel Erfolg!



Fußnoten

... Stack1
Es gibt unäre und binäre Operatoren, die also genau einen bzw. genau zwei Operanden benötigen.


Norbert Heidenbluth 2006-05-08