Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
ADT 21.02.2008
Als Zwischenschritt beim Kompilieren wird der Baum eines arithmetischen Ausdrucks in einer
Datenstruktur gespeichert. Gegeben sei dazu folgender ADT Expr :
number: R → Expr
binop: Expr × { +, − , ∗ , / } × Expr → Expr
left: Expr → Expr
right: Expr → Expr
numops: Expr → N
commutate: Expr → Expr
Die nötigen Axiome für left und right seien bereits gegeben:
A1: left(number(q)) = null
A2: left(binop(a,op,b)) = a
A3: right(number(q)) = null
A4: right(binop(a,op,b)) = b
a) Welche der gegebenen Funktionen dienen als Konstruktoren?
alles außer numops
b) Geben Sie Axiome für die Funktion numops an, welche die Zahl der arithmetischen Operationen
liefert, die der Ausdruck enthält.
numops(binop(a,op,b))=1+binop(numops(a),op,numops(b))
c) Geben Sie Axiome für die Funktion commutate an, welche auf alle Summen und Produkte
innerhalb des Ausdrucks das Kommutativgesetz anwendet (a + b = b + a und a ∗ b = b ∗ a).
commutate(binop(a,op,b) = binop(communtate(b),op,commutate(a)) falls op gleich + oder *
binop(communtate(a),op,commutate(b))
d) Reduzieren Sie den Ausdruck durch Anwendung von Axiomen auf Normalform (nicht rechnen!).
Geben Sie die Zwischenschritte und angewandten Axiome an:
binop(left(commutate(binop(4,+,7))),,right(binop(binop(1,-,1),+,binop(3,,4))))
=binop(left(binop(7,+,4)),,right(binop(0,+,12)))
=binop(7,,12)
mal ein wenig abgekürzt 
für b und c fällt mir nicht der basisfall ein 
hoffe wenigstens der rest ist so weit in ordnung
Als Basisfall für b würde ich glaub’ sowas nehmen wie:
numops(number(R)) = 0
für c dann das gleiche
commutate(number(R)) = number(R)
bei der d) wäre meine Normalform:
binop(7, * , binop(3, *, 4))
Es wird ja extra darauf hingewiesen, dass nicht gerechnet werden soll.
ist hier nicht das commutate verschuettet gegangen?
kommt am ende doch
[m]binop(4, *, binop(3, *, 4)[/m] raus?
Nein, das commutate wurde beachtet, denn
left(commutate(binop(4, +, 7)) = left(binop(7, +, 4)) = 7 (und das hat er ja an der Stelle in seiner Lösung)
Insgesagt ist die Lösung also
binop(7, *, binop(3, *, 4))
joar stimmt schon, versteh auch nicht mehr was ich da gestern falsch gesehen hab. sry. x_X
Muesste das nicht numops(binop(a,op,b)) = 1 + numops(a) + numops(b) sein?
stimmt, das binop muss weg, danke
Hat jemand auch eine Lösung zur e)? Oder zumindest eine Idee?
Unsere Idee wäre:
if(numops(op) == 0) {
return 0;
}
if(numops(left) != 0) {
left = binop(left(left), op, right(left));
}
if(numops(right) != 0) {
right = binop(left(right), op, right(right);
}
return evaluate();Ohne mir die Aufgabe genau angeschaut zu haben und somit ohne Gewähr:
double left = this.left.evaluate();
double right = this.right.evaluate();
switch(op){
case '+': return left + right;
case '-': return left - right;
case '*': return left * right;
default: return left / right;
}ich glaub ich würd’s so versuchen. Man muss zuerst die Ausdrücke links und rechts in der BinExpr auswerten und diese dann eben anhand des Operators verarbeiten.
Was du da geschrieben hast ist übrigens eine Rekursion die niemals aufhört, selbst wenn es so Fehlerfrei wäre da du im evaluate() die evaluate nochmal aufrufst ohne was an der Anzahl der Operatoren zu ändern d.h. ist numops einmal != 0 so ist es immer != 0.
Dann sind da noch folgende “Fehler”:
Numops auf einen Operator ist nicht definiert.
Was du in den ifs machst macht aus einem Term wie
(2 + 3) * …
einfach nur
(2 * 3) * …
da du im Linken teil von * nur den Operator ersetzt.
Dein Ansatz ist also ziemlich kaputt :-/
Mit dem switch ist natürlich eine elegante Lösung!
Sehe ich das richtig, dass du durch
double left = this.left.evaluate();es hinbekommst, dass evtl. vorhandene verschachtelungen auch aufgelöst werden? Aber was passiert, wenn von Anfang an left oder right nicht tiefer verschachtelt sind, also direkt einen wert haben? dann gibt doch this.left.evaluate(); was falsches zurück bzw. gar nichts oder?
wie gesagt ich hab mir die Aufgabe nicht genau angeschaut. Wenn links und rechts ein binärer Ausdruck steht, gehts problemlos. wenn links und rechts jeweils eine Zahl steht gehts auch, da die evaluation Funktion auch auf Zahlen implementiert ist laut Angabe. leer kann es links und rechts net sein, weil sonst das ADT verletzt ist… wenn es sonst noch eine Fall gibt, dann gehts natürlich kaputt…