Seite 1 von 2
Verfasst: Donnerstag 15. April 2004, 15:36
von Dookie
Hi lara,
self.data ist entweder ein int oder ein string. Wenn self.data ein int ist, braucht nichts berechnet werden, weil self dann einen Endknoten darstellt der eine Zahl beinhaltet. Wenn self.data ein string ist, dann enthält self.data den Operator +, -, /, *, ** als Asciistring.
Die Datenstruktur von Node kannst Du dir so Vorstellen.
Code: Alles auswählen
struct Node {
left Node;
right Node;
data Int or String;
}
Sorry, mein C ist etwas eingerostet, ich hoffe Du wirst daraus schlau.
Da bei Python praktisch alle Daten Objekte sind, kann ich bei self.data ein Int oder einen String verwenden. Bei C würdest Du wohl einen String verwenden der dann als String die Zahl oder einen Operator enthält.
Im Fall, daß self.data eine Zahl enthält muss diese dann immer in einen Int umgewandelt werden um damit zu rechnen. Du könntest auch 2 Felder, "operator" und "Zahl" verwenden, von denen dann immer nur eines verwendet wird, je nachdem ob ein innerer Knoten mit einem Operator oder ein äusserer Knoten mit einer Zahl vorliegt.
Bei GetValue wird mit
if type(self.data) is int: getestet ob self.data ein int ist, wenn ja wird der wert so zurückgegeben, ansosnten muss self.data den Operator symbolisieren und die Operation wird ausgerechnet, was dann zu einem recursiven Aufruf von GetValue mit den Instanzen self.left und self.right führt.
Den Parser für Deine Problemstellung kannst Du noch stark vereinfachen.
erstmal schaust Du ob eine Klammer vorhanden ist, ansonst muss da eine Zahl stehen. Je nach dem übersptingst Du die Klammer mit find_parenthesis() oder lässt den Zähler
i solange über den Ausdruck iterieren, bis auf ein "nicht numerisches Zeichen" gestossen wird. Da muss ein Operator kommen und danach wieder ein geklammerter Ausdruck oder eine Zahl kommen. Aufpassen musst Du noch da "+" und "-" ja auch ein Vorzeichen sein können.
Gruß
Dookie
Verfasst: Donnerstag 15. April 2004, 20:32
von hans
Hallo Lara
eigentlich wäre es besser gewesen, wenn du einen neuen Thread aufgemacht hättest mit Bezug auf diesen Thread. Das ist dann irgendwie übersichtlicher. Bitte das nächste mal daran denken.
Danke
Hans
geklammerte ausdrücke
Verfasst: Freitag 16. April 2004, 16:19
von lara
Hallo Dookie,
Danke für deine schnelle Antwort:)
Denke mir ist das jetzt klar gweorden mit der Datenstruktur des Suchbaumes.
Allerdings hab ich noch eine andere kleine Frage zu Aufbau des Baumes.
Beispiel: 3+4*3
Hier ist das vorgehen klar durchsucht den Ausdruck bis das + kommt da
es die kleínste Priorität hat.danach wird der rechte Ausdruck weiter bearbeitet.
(3+3)*(3+4)
Doch wie ist das vorgehen bei Klammern? genauso? Da in der Wurzel ja jetzt das mal stehen müßte!?
Außerdem hab ich noch ein ein kleines Prob mit dem parser
Code: Alles auswählen
def parse(ausdruck):
op = ""
op_at = -1
i = 0
if ausdruck[i] == "(":
while i < len(ausdruck):
if ausdruck[i] == "(":
i = find_parenthesis(ausdruck, i)+1
if i >= len(ausdruck):
break
if ausdruck[i] in "+-*/":
if ausdruck[i:i+2] == "**":
found = "**"
else:
found = ausdruck[i]
op = found
op_at = i
i += len(found)
if ausdruck[i] in "+-":
i += 1
else:
i += 1
if op_at >= 0:
return op, ausdruck[:op_at], ausdruck[op_at+len(op):]
else:
print "Fehler beim parsen von %s" % ausdruck
return None, None, None
else:
raise ValueError("Ausdruck nicht geklammert")
Allerdings wird jetzt immer die Fehlermeldung angezeigt.
Wohl wegen der Rekursion oder?
Kann ich die While Schelife überhaupt verwenden oder mus ich den Ausdruck nur mit if Anweisungen durchgehen.
Und das deine C Kenntnisse eingerostet sind macht ja nicht das krieg ich schon hin dafür bist du ja nen Crack in Python.
Vielen Dank für deine Hilfe
Gruß Lara
Verfasst: Freitag 16. April 2004, 18:05
von Dookie
Hi lara,
beim meinem Beispiel werden Klammern immer übersprungen. Daher kommt das Mal in die Wurzel, ist ja der Einzige Operator und damit der mit der kleinsten Priorität in der aktuellen Klammerebene die beiden Plus sind dann jeweils eine Ebene höher und werden hier gar nicht beachtet.
Bei deinem Parser musst Du noch prüfen, wenn er nicht mit einer Klammer beginnt, ob der Ausdruck nur aus einer Zahl besteht. Bzw. vor dem Aufrufen des Parsers dieses feststellen.
Beispiel: (3+4)
wird vom Parser Zerlegt in "+", "3", "4"
wenn dann "3" und "4" geparst werden kommt natürlich die Fehlermeldung
Mach einfach ein print ausdruck am Anfang von parse:
Dann siehst Du welchen Ausdruck der parser jeweils bekommt, und bei welchem Ausdruck der Fehler auftritt.
Gruß
Dookie
geklammerte ausdrücke
Verfasst: Sonntag 18. April 2004, 18:40
von lara
Hallo,
irgendwie häng ich durch.
Hab den Code erweitert im Hauptptogarmm um abzufragen ob der Ausdruck mit ner Klammer beginnt.
Code: Alles auswählen
def find_parenthesis(ausdruck, index):
cnt = 1
if ausdruck[index] == "(":
for i in xrange(index+1, len(ausdruck)):
if ausdruck[i] == "(":
cnt += 1
elif ausdruck[i] == ")":
cnt -= 1
if cnt == 0:
break
elif ausdruck[index] == ")":
for i in xrange(index-1, -1,-1):
if ausdruck[i] == ")":
cnt += 1
elif ausdruck[i] == "(":
cnt -= 1
if cnt == 0:
break
if cnt != 0:
raise ValueError("unbalanced parentesis")
return i
def parse(ausdruck):
print ausdruck
op = ""
op_at = -1
i = 0
while i < len(ausdruck):
if ausdruck[i] == "(":
i = find_parenthesis(ausdruck, i)+1
if i >= len(ausdruck):
break
if ausdruck[i] in "+-*/":
if ausdruck[i:i+2] == "**":
found = "**"
else:
found = ausdruck[i]
op = found
op_at = i
i += len(found)
if ausdruck[i] in "+-":
i += 1
else:
i += 1
if op_at >= 0:
print "links",ausdruck[:op_at]
print "rechts", ausdruck[op_at+len(op):]
return op, ausdruck[:op_at], ausdruck[op_at+len(op):]
else:
print "Fehler beim parsen von %s" % ausdruck
return None, None, None
class Node(object):
def __init__(self, ausdruck):
while (ausdruck[0] == "(" and
find_parenthesis(ausdruck, 0) == len(ausdruck)-1):
ausdruck = ausdruck[1:-1]
print "node", ausdruck
try:
self.data = int(ausdruck)
self.left = None
self.right = None
except ValueError:
data, left, right = parse(ausdruck)
self.data = data
self.left = Node(left)
self.right = Node(right)
def GetValue(self):
if type(self.data) is int:
return self.data
else:
if self.data == "+":
return self.left.GetValue() + self.right.GetValue()
elif self.data == "-":
return self.left.GetValue() - self.right.GetValue()
if self.data == "*":
return self.left.GetValue() * self.right.GetValue()
elif self.data == "/":
if self.left.GetValue() % self.right.GetValue() != 0:
raise ValueError("Keine ganzzahlige Division!")
else:
return self.left.GetValue() / self.right.GetValue()
elif self.data == "**":
return self.left.GetValue() ** self.right.GetValue()
else:
return "Fehler: unbekannter Operand %s" % self.data
def print_me(self, depth=0):
indent = " "*depth
if self.left:
self.left.print_me(depth+1)
print indent+str(self.data)
if self.right:
self.right.print_me(depth+1)
if __name__ == "__main__":
import sys
while 1:
ausdruck = raw_input("Ausdruck: ")
if ausdruck == "":
sys.exit()
if ausdruck[0] == "(":
rechenBaum = Node(ausdruck)
print "Rechenbaum:"
rechenBaum.print_me()
print "Ergebnis:", rechenBaum.GetValue()
else:
raise ValueError("keine Klammer am Anfang")
Das mit den print Anweisungen war nen guter Tipp so seh ich´was wo wie zurückgeliefert wird.
Allerdings hab ich schon einiges probiert und die Node Klasse um Abfragen erweitert aber der Algorithmus war nicht universell, da es ja verschiedene Fälle gibt.
Vorallem schwierig abzufragen ist der Fall in dem mehre Operationen in einer Klammer sind was ja nicht erlaubt ist.(3+3+3)
Ich hatte es nun so gemacht in der Node Klasse zu testen ob es mehr als einen Operand gibt. Aber das kommt halt nicht immer hin.
Ich hoffe es kann mir jemand nochmal einen kleinen Tipp geben ich hab irgendwie nen Brett vorm Kopf.
Vielen Dank,
Gruß
Lara
Verfasst: Sonntag 18. April 2004, 23:15
von Dookie
Hi lara,
hier mal ein ganz einfacher Parser, der mitzählt wieviele Operatoren er findet.
Code: Alles auswählen
def parse(ausdruck):
num = 0 # Zähler für Operatoren
if ausdruck[0] in "+-":
i = 1 # zeichen an position 0 ist nur ein Vorzeichen
else:
i = 0
while i < len(ausdruck):
if ausdruck[i] == "(":
i = find_parenthesis(ausdruck, i)+1
if i >= len(ausdruck):
break
if ausdruck[i] in "+-*/": # Operator?
if ausdruck[i:i+2] == "**":
found = "**"
op_at = i
i += 1
else:
found = ausdruck[i]
op_at = i
op = found
num += 1 # Operator zählen
if ausdruck[i+1] in "+-": # Vorzeichen
i += 1
i += 1
if num != 1:
raise ValueError("Nur ein Operator erlaubt!")
return op, ausdruck[:op_at], ausdruck[op_at+len(op):]
Gruß
Dookie
Verfasst: Montag 19. April 2004, 19:48
von Dookie
Hallo,
für alle, die interessa an der Funktionsweise von Rechenbäumen haben, habe ich eine gut dokumentierte Fassung meines Rechenbaums, der mit Floats arbeitet in die Codebase hochgeladen:
Rechenbaum
Gruß
Dookie
Verfasst: Montag 19. April 2004, 20:34
von Milan
Hi. Irgendwie gibts da ein broken Link oder eine Misskonfiguration, denn: ich kann zwar über deinen Link und über die Suche in der Codebase darauf zugreifen, gehe ich aber direkt von der Hauptseite in "Algorithmen" so wird mir nichts angezeigt... Ist das normal ( --> Verzögerung ) oder ein Bug?
Milan
Verfasst: Montag 19. April 2004, 20:39
von Dookie
über die Übersicht der Codebase und in den Algorithmen wird auch nichts angezeigt, über die Suche gehts - komisch.
Gruß
Dookie
geklammerte ausdrücke
Verfasst: Montag 19. April 2004, 22:14
von lara
Hi,
Danke Dookie. So kann man es auch machen hatte es ja so ähnlich in der Node Klasse implemetiert.
Doch mein wirkliches Problem woran ich gescheitert bin ist das es bei diesem Beispiel nicht klappt:
(3+3)+3
oder((3+3)+3)
wel ja nacher nur wieder die ganz rechte 3 zurück gegeben wird und das Problem ist ja man kann es nicht allgemein auf int Ausdrücke programmieren weil ja auch die 3 en in der Klammer einzeln zurück geliefert werden.
Hast du da irgendwie nen theoretischen Ansatz weil da überleg ich schon hin und her..
Höchste Zeit schlafen zu gehen
Gruß
Lara
Verfasst: Montag 19. April 2004, 22:38
von Dookie
Hi lara,
hmm das verstehe ich jetzt nicht ganz? Klar werden die 3en als "3" zurückgeliefert, was erwartest Du daß der Parser sonst zurückliefern soll?
Gruß
Dookie
geklammerte ausdrücke
Verfasst: Dienstag 20. April 2004, 13:52
von lara
Hi,
Ja das 3 zurückgeliefert werden ist nicht schlimm.
Doch bei diesen Beispiel:
(3+3)+4
oder((3+3)+4)
müßte ja bei dem ersten Beipsiel ohne Klammerung ne Fehlermeldung kommen da +4 nich geklammert ist.
Mein Problem ist ich kann jetzt nichts universelles programmieren da ja bei dem zweiten Beispiel irgendwann der gleich Ausdruck zurückgeliefert wird.
Hast du ne Idee wie man diesen Unterschied lösen kann das unterschideden wird zwischen den beiden Fällen?
Ich hoffe ich hab es jetzt etwas besser ausgedückt..
Gruß
Lara
Verfasst: Dienstag 20. April 2004, 14:20
von Dookie
Hi auch,
ja da brauchst du ja nur vorher prüfen, ob der ganze ausdruck geklammert ist. Wenn nicht und lässt sich nicht in eine Zahl wandeln, dann gibst Du eine Fehlermeldung aus, sonst baust Du mit dem Ausdruck den Baum auf.
Gruß
Dookie
geklammerte ausdrücke
Verfasst: Dienstag 20. April 2004, 22:39
von lara
hi,
da bin ich wieder.
Ich hab das Hauptprogarmm mal ergänzt:
Code: Alles auswählen
if __name__ == "__main__":
import sys
while 1:
ausdruck = raw_input("Ausdruck: ")
if ausdruck == "":
sys.exit()
if (ausdruck[0] == "(" and
find_parenthesis(ausdruck, 0) == len(ausdruck)-1):
rechenBaum = Node(ausdruck)
print "Rechenbaum:"
rechenBaum.print_me()
print "Ergebnis:", rechenBaum.GetValue()
else:
raise ValueError("Ausdruck nicht korrekt geklammert!")
Jetzt wird dieser Fall erkannt.
((3+3)+4)
aber bei diesen Fall kommt die Fehlermeldung auch (3+3)+(3+3)
Aber der Ansatz ist doch richtig oder?
Da man dochh nur im HAuptptogramm die Abfrage machen kann oder?
Irgendwann komm auch ich ans Ziel.
Gruß
Lara
Verfasst: Mittwoch 21. April 2004, 02:16
von Dookie
Hi lara,
(3+3)+(3+3) ist nach deiner Definition ja auch nicht gültig, es muss ((3+3)+(3+3)) heissen.
3+3 ist ja auch nicht erlaubt, da muss es ja auch (3+3) heissen oder?
Gruß
Dookie
geklammerte ausdrücke
Verfasst: Mittwoch 21. April 2004, 13:21
von lara
hi,
das ist ja leider das schwierige.
(3+3)+(3+3) erlaubt
ebenso wie
((3+3)+(3+3))
und
((3+3)+3)
das ist ja das problematische. Ich verzweifel schon leicht da meine Varianten immer nur für ein Problem die Lösung ist aber nie für alle.
Ich hoffe du steigest so leicht durch.
Gruß
Lara
Verfasst: Mittwoch 21. April 2004, 18:28
von Dookie
hiho,
eingentlich musst Du nur vor dem Parsen, und nach dem alle Leerzeichen entfernt wurden, abfragen, ob der Ausduck mit einer Klammer beginnt und endet. Alle anderen Bedingungen (nur ein Rechenoperator) werden dann im Parser festgestellt.
Code: Alles auswählen
if ausdruck[0] != "(" or ausdruck[-1] != ")":
raise ValueError("Unerlaubter Ausdruck!")
Gruß
Dookie
geklammerte ausdrücke
Verfasst: Dienstag 27. April 2004, 15:50
von lara
hi,
Ich habe übrigens noch eine interssante Seite gefunden zu diesem Thema.
www.vs.inf.ethz.ch/edu/SS2000/I2/ folien/Vorl_Info2_SS00_3.pdf
Das ist doch auch der Thereitsche Ansatz so wie du das gelöst hast Dookie oder?
Der Suchbaum ist ja ein Anstz aber es gibt ja noch einen anderen.
So wie du das auch schon mal nagedeutet hast das man sich zuerst den Operator mit der höchsten Priorität sucht oder die innerste klammer und zusammenrechnet im String und die Zahl dort hinschreibt.
Oder kennst du eine Seite zu diesem theoreschen Ansatz oder kannst mir das noch ein bißchen verdeutlichen?
Beruht das auf dem Prinzip des Kellerautomaten bzw. eines Stacks?
Und ich bekomm ja nie genug desewegen hab ich noch nen kleines Prob:)
und zwar in dem Programm wo die Priortät nur durch Klammern festgelgt wird gibs noch nen kleinen Fehler.
Und zwar gibt man (3+3)+(3+3)*(3+3)
Jetzt kommt der Fehler das nur ein Operator erlaubt ist.
Also in der parse Funktion ist num = 2.
das Problem ist jetzt natürlich das der Ausdruck korrekt ist.
Würd ich also etwa bei der num Auswertung ändern würde ja dann auch wieder der Ausdruck in der Klammer beeinflusst werden wo ja auf keinen FAll 2 Operatoren erlaubt sind.
Ich hab mir schon wieder das Hirn zermattert hast du einen Ansatz dafür?
Code: Alles auswählen
def find_parenthesis(ausdruck, index):
cnt = 1
if ausdruck[index] == "(":
for i in xrange(index+1, len(ausdruck)):
if ausdruck[i] == "(":
cnt += 1
elif ausdruck[i] == ")":
cnt -= 1
if cnt == 0:
break
elif ausdruck[index] == ")":
for i in xrange(index-1, -1,-1):
if ausdruck[i] == ")":
cnt += 1
elif ausdruck[i] == "(":
cnt -= 1
if cnt == 0:
break
if cnt != 0:
raise ValueError("unbalanced parentesis")
return i
def parse(ausdruck):
num = 0
if ausdruck[0] in "+-":
i = 1
else:
i = 0
while i < len(ausdruck):
if ausdruck[i] == "(":
i = find_parenthesis(ausdruck, i)+1
if i >= len(ausdruck):
break
if ausdruck[i] in "+-*/":
if ausdruck[i:i+2] == "**":
found = "**"
op_at = i
i += 1
else:
found = ausdruck[i]
op_at = i
op = found
num += 1
if ausdruck[i+1] in "+-":
i += 1
i += 1
if num != 1:
raise ValueError("Nur ein Operator erlaubt!")
print op
print "links" , ausdruck[:op_at]
print "rechts", ausdruck[op_at+len(op):]
return op, ausdruck[:op_at], ausdruck[op_at+len(op):]
class Node(object):
def __init__(self, ausdruck):
while (ausdruck[0] == "(" and
find_parenthesis(ausdruck, 0) == len(ausdruck)-1):
ausdruck = ausdruck[1:-1]
try:
self.data = int(ausdruck)
self.left = None
self.right = None
except ValueError:
data, left, right = parse(ausdruck)
self.data = data
self.left = Node(left)
self.right = Node(right)
def GetValue(self):
if type(self.data) is int:
return self.data
else:
if self.data == "+":
return self.left.GetValue() + self.right.GetValue()
elif self.data == "-":
return self.left.GetValue() - self.right.GetValue()
if self.data == "*":
return self.left.GetValue() * self.right.GetValue()
elif self.data == "/":
if self.left.GetValue() % self.right.GetValue() != 0:
raise ValueError("Keine ganzzahlige Division!")
else:
return self.left.GetValue() / self.right.GetValue()
elif self.data == "**":
return self.left.GetValue() ** self.right.GetValue()
else:
return "Fehler: unbekannter Operand %s" % self.data
def print_me(self, depth=0):
indent = " "*depth
if self.left:
self.left.print_me(depth+1)
print indent+str(self.data)
if self.right:
self.right.print_me(depth+1)
if __name__ == "__main__":
import sys
while 1:
ausdruck = raw_input("Ausdruck: ")
if ausdruck == "":
sys.exit()
if ausdruck[0] != "(" or ausdruck[-1] != ")":
raise ValueError("Unerlaubter Ausdruck!")
rechenBaum = Node(ausdruck)
print "Rechenbaum:"
rechenBaum.print_me()
print "Ergebnis:", rechenBaum.GetValue()
Gruß
Lara
Verfasst: Dienstag 27. April 2004, 16:05
von Dookie
Hi lara,
mal erlaubt, mal nicht erlaubt, wo hast Du die Problemstellung her?
Du müsstest an den Parser mitübergeben, auf welcher (Klammer-)Ebene er sich befindet, und auf der ersten mehr als einen Operator erlauben und auf jeder anderen nur einen.
Mein 2. Ansatz arbeitet eigentlich auch mit einer Baumstruktur, nur ist diese in den recursiven Aufrufen der Rechenfunktion verborgen. Steckt also quasi in der Funktion selbst.
Gruß
Dookie
geklammerte ausdrücke
Verfasst: Dienstag 27. April 2004, 23:24
von lara
HI,
ich hab den parser erweitert.
Code: Alles auswählen
def parse(ausdruck):
num = 0
klam = 0
i1 = 0
if ausdruck[0] in "+-":
i = 1
else:
i = 0
while i < len(ausdruck):
if ausdruck[i] == "(":
i = find_parenthesis(ausdruck, i)+1
klam += 1
if i >= len(ausdruck):
break
if ausdruck[i] in "+-*/":
if ausdruck[i:i+2] == "**":
found = "**"
op_at = i
i += 1
else:
found = ausdruck[i]
op_at = i
op = found
num += 1
if ausdruck[i+1] in "+-":
i += 1
i += 1
if klam == 0 :
if num != 1:
raise ValueError("Nur ein Operator erlaubt!")
print op
print klam
print "links" , ausdruck[:op_at]
print "rechts", ausdruck[op_at+len(op):]
return op, ausdruck[:op_at], ausdruck[op_at+len(op):]
so gehts eigentlich wenn ich nicht etws übersehen hab.
Also bisher mein ich immer das gleiche.Vielleicht habe ich mich ja auch Mißverständlich ausgedrückt manchmal
Allerdings nichts geht ohne Probs.
(3+3)+3+(3+3)
dieser Asudruck wird jetzt auch aktzeptiert obwohl die 3 geklammert sein müßte damit er aktzeptiert wird.
Eigentlich müßte ich testen ob jeder Ausdruck gelammert ist doch dann gibs wieder Pribs bei diesem Ausdruck.
((3+3)+3)
der ja auch zulässig wäre.
Hast du da noch eine Idee?
2. Hast du dir den Link oben mal angeguckt? wie der BAum aufgebaut wird ist klar. Doch wird auch mit nem Stack gearbietet oder wo und wie werden die Werte des BAumes gespeichert?
3. Zu einem anderen Ansatz. wenn man jeweils bei dem mit der höchsten Priorität anfängt und dann zusammen rechnet. Inwiefern wird da auch nen Baum aufgebaut. Ist das denn überhaupt nötig?
Oh ist es spät:)
Dank dir schon im vorraus.Weiß ich bin nen kleiner Quälgeist.
Gruß
Lara