geklammerte ausdrücke einlesen und berechnen

[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

[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

[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

[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:

Code: Alles auswählen

def parse(ausdruck):
    print ausdruck
    op = ""
    ...

Dann siehst Du welchen Ausdruck der parser jeweils bekommt, und bei welchem Ausdruck der Fehler auftritt.


Gruß

Dookie

[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

[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

[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

[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

[Dookie]

über die Übersicht der Codebase und in den Algorithmen wird auch nichts angezeigt, über die Suche gehts - komisch.


Gruß

Dookie

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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