WS 2002/2003 Übung 7
H. Schweppe
(wegen Klausur am 10.12. verkürzt)
Ausgabe: 28.11.2002
Abgabe: 10.12.2002
15.00
Aufgabe 7.1 ( 11 P)
Boolesche Ausdrücke, wie true OR (true AND false) AND true werden intern oft mit sogenannten Operatorbäumen repräsentiert. Der obige Ausdruck z.B. läßt sich darstellen als:
Hierbei stehen die booleschen Operatoren in den
Knoten und die boolesche Werte in den Blättern des Baumes. Im Paket boolexp (siehe
http://www.inf.fu-berlin.de/lehre/WS02/ALP3/uebungen/A7-2.zip)
finden Sie Programmgerüste, mit deren Hilfe man
solche Ausdrücke bearbeiten (ausgeben / auswerten) kann. Das Unterverzeichnis,
in die Sie die Datei entpacken, sollte
boolexp heißen.
a) (2) Geben Sie für die Klassen: BoolExpression,
BoolOperator, BoolLiteral, And und
Or das Vererbungsdiagramm an.
b) (4) Vervollständigen Sie die Klassen und testen es mit folgendem Programm:
package boolexp;
public class Test {
public static void main(String argv[]) {
BoolExpression boolexpr =//entspricht true OR (true
AND false) AND true
new Or(new BoolLiteral(true),
new And(new And(new BoolLiteral(true),
new BoolLiteral(false)),
new
BoolLiteral(true)));
// Die zu schreibende Klasse zum Durchlaufen (traversieren)
der Baeume
//
CalculateTraverser c = new CalculateTraverser();
// boolexpr.accept(c);
//
System.out.println(" = " + c.getResult());
}
}
c) (5) Schreiben Sie eine Klasse namens
boolexp.CalculateTraverser,
die das Interface boolexp.Traverser implementiert.
Diese Klasse soll das Ergebnis eines booleschen Ausdrucks berechnen.
Aufgabe 7.2 ( 9 P)
a) (3)Zeichen Sie einen Binärbaum T so dass:
- Jeder innere Knoten ein Zeichen enthält.
- Der preorder-Durchlauf der Knoten von T die Zeichenkette
"informatik" liefert.
- Der inorder-Durchlauf der Knoten von T die Zeichenkette
"ofrnmitaki" liefert.
b)(3) Schreiben Sie eine Haskell-Funktion, die die Knoten eines Binärbaums vom
Typ
data
BT1 t =
Empty | N (BT1 t)
(BT1 t) t
in postorder-Folge durchläuft.
c)(3)
Zeigen Sie, dass Folgendes in jedem Binärbaum gilt: ist x die
Anzahl der Knoten vom Grad 2 und b die Anzahl Blätter, so ist b= x+1 .
Hinweis: durch Induktion .
20 Punkte