Not logged in. · Lost password · Register

Forum: Bachelor › Algorithmik › Algorithmen und Datenstrukturen RSS
ADT 21.02.2008
Danieru
Member since Nov 2009
258 posts
 2010-08-01, 18:23   #1  
Subject: 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
Das F
Avatar
Member since Apr 2009
632 posts
 2010-08-01, 19:16   #2  
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.
"Na całe szczęście wiem jak radę dać bez wiary" - Piotr Rogucki
ull
Member since May 2009
186 posts
 2010-08-03, 17:41   #3  
In reply to post #1
Quote by Danieru on 2010-08-01, 18:23:
....
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)
....

ist hier nicht das commutate verschuettet gegangen?

kommt am ende doch
binop(4, *, binop(3, *, 4) raus?
ɹǝʇndɯoɔ ɥʇıʍ pooƃ ʇou ɯɐ ı ǝɹǝɥ ʇǝƃ sıɥʇ pıp ʍoɥ poƃ ɥo
neverpanic
Member since Sep 2008
1458 posts
 2010-08-03, 17:59   #4  
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))
This post was edited on 2010-08-03, 18:00 by neverpanic.
ull
Member since May 2009
186 posts
 2010-08-04, 09:49   #5  
joar stimmt schon, versteh auch nicht mehr was ich da gestern falsch gesehen hab. sry. x_X
ɹǝʇndɯoɔ ɥʇıʍ pooƃ ʇou ɯɐ ı ǝɹǝɥ ʇǝƃ sıɥʇ pıp ʍoɥ poƃ ɥo
rudis
SPler
(Administrator)
Member since Apr 2010
649 posts
 2010-08-04, 13:08   #6  
In reply to post #1
Quote by Danieru on 2010-08-01, 18:23:
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))

Muesste das nicht numops(binop(a,op,b)) = 1 + numops(a) + numops(b) sein?
Danieru
Member since Nov 2009
258 posts
 2010-08-04, 13:17   #7  
stimmt, das binop muss weg, danke
matze_
Member since Oct 2011
113 posts
 2012-07-10, 16:38   #8  
Hat jemand auch eine Lösung zur e)?  Oder zumindest eine Idee?
Unsere Idee wäre:
  1. if(numops(op) == 0) {
  2.  return 0;
  3. }
  4. if(numops(left) != 0) {
  5.   left = binop(left(left), op, right(left));
  6. }
  7. if(numops(right) != 0) {
  8.   right = binop(left(right), op, right(right);
  9. }
  10. return evaluate();
This post was edited on 2012-07-10, 16:44 by matze_.
Das F
Avatar
Member since Apr 2009
632 posts
 2012-07-11, 13:19   #9  
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 :-/
"Na całe szczęście wiem jak radę dać bez wiary" - Piotr Rogucki
matze_
Member since Oct 2011
113 posts
 2012-07-11, 20:32   #10  
Mit dem switch ist natürlich eine elegante Lösung!
Sehe ich das richtig, dass du durch
  1. 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?
Das F
Avatar
Member since Apr 2009
632 posts
 2012-07-11, 22:40   #11  
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...
"Na całe szczęście wiem jak radę dać bez wiary" - Piotr Rogucki
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:

Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen