geklammerte ausdrücke einlesen und berechnen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Donnerstag 15. April 2004, 15:36

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
Zuletzt geändert von Dookie am Dienstag 13. Juli 2004, 17:23, insgesamt 1-mal geändert.
hans
User
Beiträge: 728
Registriert: Sonntag 22. September 2002, 08:32
Wohnort: Sauerland
Kontaktdaten:

Donnerstag 15. April 2004, 20:32

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
User
Beiträge: 9
Registriert: Donnerstag 15. April 2004, 14:55

Freitag 16. April 2004, 16:19

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. :wink:

Vielen Dank für deine Hilfe

Gruß Lara
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Freitag 16. April 2004, 18:05

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
Zuletzt geändert von Dookie am Dienstag 13. Juli 2004, 17:21, insgesamt 1-mal geändert.
lara
User
Beiträge: 9
Registriert: Donnerstag 15. April 2004, 14:55

Sonntag 18. April 2004, 18:40

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
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Sonntag 18. April 2004, 23:15

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
Zuletzt geändert von Dookie am Dienstag 13. Juli 2004, 17:20, insgesamt 1-mal geändert.
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Montag 19. April 2004, 19:48

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
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Montag 19. April 2004, 20:34

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
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Montag 19. April 2004, 20:39

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


Gruß

Dookie
lara
User
Beiträge: 9
Registriert: Donnerstag 15. April 2004, 14:55

Montag 19. April 2004, 22:14

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 :lol:
Gruß

Lara
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Montag 19. April 2004, 22:38

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
User
Beiträge: 9
Registriert: Donnerstag 15. April 2004, 14:55

Dienstag 20. April 2004, 13:52

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
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Dienstag 20. April 2004, 14:20

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
User
Beiträge: 9
Registriert: Donnerstag 15. April 2004, 14:55

Dienstag 20. April 2004, 22:39

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. :D
Gruß

Lara
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Mittwoch 21. April 2004, 02:16

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
Antworten