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