Das deutsche Python-Forum

Hi lara,

hier mal ein ganz einfacher Parser, der mitzählt wieviele Operatoren er findet.

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

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

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

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

Gruß

Dookie

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

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

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

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

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

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

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

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

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

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

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

Hi lara,

1. woher hast Du eigentlich die Aufgabe (hab ich schonmal gefragt), logisch ist das ganze eigentlich nicht mehr und es entbehrt für mich auch einer gewissen Sinnhaftigkeit. Idee hab ich dazu jetzt auch keine mehr.

2. den Link hab ich mir angeguckt, aber ich hab im moment echt nicht die Zeit mich durch die ganzen pdf's zu arbeiten.

3. es wird eben kein Baum explizit aufgebaut, aber der rekursive Aufruf der Funktion bildet wenn man sich die geschachtelten Funktionsaufrufe vorstellt einen Baum. So wie mit einer rekusiven Funktion ein Rechenbaum durchlaufen wird, arbeitet sich meine Funktion direkt durch den angegebenen Ausdruck.

Gruß

Dookie *dergequälte*

Hallo,

kann jemand so nett sein mir schnell nochmal die Funtktion print_me die zur grafischen Darstellung des Rechenbaumes dient erklären?

Gruß

calanetics

Hi Calanetics,

print_me durchläuft rekursiv den Baum "inorder" also (falls vorhanden) zuerst linken Teilbaum, dann den Operator oder Wert aus self.data und dann (falls vorhanden) rechten Teilbaum. Für die Einrückung wird noch die Rekursionstiefe als Parameter mitgegeben.

Gruß

Dookie

Da jetzt die Klausuren vorbei sind, wurde dieser Thread wieder hierher zurückgelegt.

Gruß

Dookie

Das deutsche Python-Forum

geklammerte ausdrücke einlesen und berechnen

geklammerte ausdrücke

geklammerte ausdrücke

geklammerte ausdrücke

geklammerte ausdrücke

geklammerte ausdrücke

geklammerte ausdrücke

geklammerte ausdrücke

Wieder da.