Das deutsche Python-Forum

Seit 2002 Diskussionen rund um die Programmiersprache Python
https://www.python-forum.de/

geklammerte ausdrücke einlesen und berechnen

https://www.python-forum.de/viewtopic.php?t=1392

Seite 1 von 2

geklammerte ausdrücke einlesen und berechnen

Verfasst: Sonntag 28. März 2004, 14:53
von TripleH
Hi,
Ich hoffe ihr könnt mir langsam helfen auf meinem langen Weg.Ich hab ne Aufgabe die ich mit Hilfe von Python lösen möchte. Ich hab zwar schon gute Kenntnisse aber bin leider nch kein Genie und bau auf Eure Erfahrungen.
Hier die Aufgabe:

I. Schreiben Sie ein Programm „Auswertung“, das zulässige, geklammerte Ausdrücke einliest und berechnet, wobei zulässige Ausdrücke wie folgt aufgebaut sind:

Die Eingabewerte sind ganzzahlig und der Ausdruck wird vollständig übergeben, d.h. als vollständige Zeile oder als Datei. Als Operatoren können + (Addition), - (Subtraktion), * (Multiplikation), / (ganzzahlige Division ohne Rest), und **2 ( Quadrierung ) auftreten, wobei die Operanden auch mathematisch geklammert sein können ( Klammersymbole ( oder ) ). Als Trennzeichen fungiert das Leerzeichen; eine Folge von Trennzeichen ist einem einzelnen Trennzeichen gleichwertig. Vor und hinter jedem Operator darf ein Trennzeichen stehen, braucht es aber nicht. Ein Zeilenende-Zeichen beendet einen Ausdruck.

Das Programm erfüllt folgende Anforderungen/Funktionen:

Lesen und Berechnung werden wiederholt, bis das Dateiende-Zeichen erreicht wird. Die Umleitung der Eingabe in eine Datei ist möglich, d.h. Dateien mit zulässig geklammerten Ausdrücken können zur Auswertung an das Programm übergeben werden.
Das Programm sieht (mindestens) für folgende Fälle verschiedene Fehlermeldungen vor:
Unzulässige Eingaben ( Aufgabe: welche unzulässigen Eingaben können entstehen ??? ).
Bereichsüberschreitungen beim Rechnen.

So denk mal so ne Aufageb ist nicht ganz neu aber seh ich das richtig:
das zulässig dieser ausdruck ist (3+3*(4-1))
aber ist auch dier ausdruck zulässig 3+3*(4-1)?
Es ist doch nicht Plicht das die Zeile mit ner Klammer beginnt sondern nur das die Klmmern richtig gesezt sind oder?

2. Die Eingabewerte sind ganzzahlig und der Ausdruck wird vollständig übergeben, d.h. als vollständige Zeile oder als Datei

heißt das beides muss möglich sein?

3.so zu tehoretischen überlegung.zuerst muss ich doch prüfen ob die klammern richtig sind und dan ventuelle leerzeichen rausmachen.
danach müßt ich dann irgendwie mir überlegen wie er nen poetenz(**) erkennt was heißt das er immer 2 Zeichen vorraus prüfen muss.
Ich hab mich belesen und die polnische notation gefunden.ist das der richtigen ansatz?


Ich hoffe ihr könnt mir weiterhelfen das ich diese aufgabe erfolgreich schaffe und vorallem auch ne Menge lerne und habt geduld.
Vielen Dank im voraus.

mfg lara

Verfasst: Sonntag 28. März 2004, 16:11
von MacEvil
eval(ausdruck) :wink:

Verfasst: Montag 29. März 2004, 00:01
von Dookie
Hi TripleH,

IMHO ist auch 3+3*(4-1) korrekt.

Beginne mit einem einzelnen Ausdruck. Für mehrere Ausdrücke in mehreren Zeilen, lässt sich das dann leicht erweitern.

zuallererst die Whitespaces am Beginn und am Ende(auch den Zeilenvorschub am Ende), und alle Leerzeichen entfernen mit

Code: Alles auswählen

ausdruck = ausdruck.strip()
ausdruck = ausdruck.replace(" ", "")
das würde ich in der Hauptfunktion machen, von der aus dann die eigentliche Auswertungsfunktion aufgerufen wird. Da du um einen recursiven Algorithmus kaum herumkommen wirst, würde sonst bei jedem Aufruf sinnloserweise das Löschen nicht mehr vorhandener Leerzeichen erfolgen.

Dann würde ich eine Funtion machen, um zu jeder Klammer im Ausdruck das passende Gegenstück zu finden.

Code: Alles auswählen

def find_parenthesis(ausdruck, index):
    cnt = 1 # Zähler für Klammervarschachtelung
    if ausdruck[index] == "(":
        for i in xrange(index+1, len(ausdruck)):
            if ausdruck[i] == "(":
                cnt += 1
            elif ausdruck[i] == ")":
                cnt -= 1
            if cnt == 0: # schliessende Klammer gefunden
                break # fertig, i enthält den Index
    elif ausdruck[index] == ")":
        for i in xrange(index-1, -1,-1):
            if ausdruck[i] == ")":
                cnt += 1
            elif ausdruck[i] == "(":
                cnt -= 1
            if cnt == 0: # öffnende Klammer gefunden
                break # fertig, i enthält den Index
    else:
        raise ValueError("'%s' is not a parentesis" % ausdruck[index])
    if cnt != 0:
        raise ValueError("unbalanced parentesis")
    return i
Mit dieser Funktion kannst Du auch leicht testen, ob der ganze Ausdruck geklammert ist, und gegebenenfalls die äussersten Klammern löschen.

Code: Alles auswählen

while (ausdruck[0] == "(" and 
          ausdruck[-1] == ")" and
	  find_parenthesis(audruck,0) == len(ausdruck)-1)
	  ausdruck = ausdruck[1:-1]
Damit haben wir mal eine Basis um Leerzeichen und Klammerungen zu behandeln.

Bevor wir ans parsen (zerlegen in einzelne Teile) des Ausdrucks gehen, überleg dir z.B. bei "3+3*(4-1)", in welcher Reihenfolge die einzelnen Operationen ausgeführt werden müssen. (Ich gehe davon aus, daß auch bei Deinem Beispiel Punkt- vor Strichrechnung geht.)
erstmal kommt, wegen der Klammer
4-1 = 3
neuer Ausdruck 3+3*3
dann kommt, Punkt vor Strich
3*3 = 9
neuer Ausdruck 3+9 = 12
12 ist das Ergebnis.

Jetzt könnte man natürlich im Ausdruck immer die Operation, mit der höchsten Priorität heraussuchen (Punkt vor Strich, innerste Klammer) und, im String, durch das Ergebnis ersetzen.
Da kommen aber sehr schnell unzählige Stringoperationen zusammen und es müsste immer wieder, eigentlich schon Geparstes, untersucht werden.
Um das zu vermeiden, verwendet man einen sogenannten Rechenbaum.

Code: Alles auswählen

          4   1
           \ /
        3   -
         \ /
      3   *
       \ /
        + wurzel
Jeder Endknoten eines solchen Baumes stellt eine Zahl dar, und jeder innere Knoten einen Operator. Du kannst Dir ja mal überlegen, wie eine Klasse für so einen Knoten ausschauen könnte, und wie du aus dem Ausdruck "3+3*(4-1)" einen solchen Baum aufbauen kannst.
TIPP: wenn jeder Knoten, eine Methode "get_value()" hat, welche im Falle eines äusseren Knotens einfach die Zahl zurück gibt, und im Falle eines inneren Knotens das Ergebnis der Berechnung, self.links.get_value() self.operator self.rechts.get_value() zurückgibt. Ergibt der Aufruf von wurzel.get_value() Das Ergebnis des Ausdrucks.
Die Methode "get_value()" könnte so ausschaun:

Code: Alles auswählen

    def get_value(self):
        if self.data == "+":
        return self.left.get_value() + self.right.get_value()
    elif self.data == "-":
        return self.left.get_value() - self.right.get_value()
    ... # noch für * / und ** definieren
    else:
        return int(self.data)
Ein Beispiel für einen Rechenbaum, allerdings in Java findest Du auf:
Java-Rechenbaum

So das sollte erstmal reichen.


Gruß

Dookie

geklammerte Ausdrücke

Verfasst: Mittwoch 31. März 2004, 11:45
von TripleH
Hallo,

Danke Dookie für deine nette Hilfe. An dem Quelltext für den Suchbaum arbiete ich zur Zeit und natürlich auch viel lesen und probieren denn ist nich ganz so einfach die Sache.

Als erstes damit es einfacher ist brauch ich Punkt vor Strichrechnung nicht beachten da durch die richtige Klammerung es garnicht zu der Frage kommen soll.

Code: Alles auswählen

def find_parenthesis(ausdruck, index):
    cnt = 0 # Zähler für Klammervarschachtelung
    if ausdruck[index] == "(":
        for i in xrange(index+1, len(ausdruck)):
            if ausdruck[i] == "(":
                cnt += 1
            elif ausdruck[i] == ")":
                cnt -= 1
            if cnt == 0: # schliessende Klammer gefunden
                break # fertig, i enthält den Index
    elif ausdruck[index] == ")":
        for i in xrange(index-1, -1,-1):
            if ausdruck[i] == ")":
                cnt += 1
            elif ausdruck[i] == "(":
                cnt -= 1
            if cnt == 0: # öffnende Klammer gefunden
                break # fertig, i enthält den Index
    else:
     
    if cnt != 0:
        raise ValueError("unbalanced parentesis")
    return i geht dann nicht mehr
Allerdings hab ich noch nen par kleine Fragen zum Quelltext. Zum einen hab ich den counter Anfang auf 0 gesetz und die eine Fehlermeldung rausgenommen. Ich hoff ich seh das richtig so oder?Weil der Ausdruck ja nich zwingend mit einer Klammer beginnen muss. Allerdings gibs jetzt noch nen prob das er dann gleich zu else Anweisung springt wenn erst später ne Klammer kommt.
Aber nun meine Fragen:

1.
Meine erste Frage ist später im Hauptprogramm den ich mal das wir immer mit index 0 arbeiten werden beim Aufruf oder.

2. for i in xrange(index-1, -1,-1):
wie ist diese Zeile zu interpreitieren?

So an dem Suchbaum arbeit ich da meld ich mich die Tage nochmal.

Hab Dank

Bis danni

Verfasst: Mittwoch 31. März 2004, 21:16
von Dookie
Hi TripleH,

ich bin es halt gewohnt, für Funktionen eher englische als deutsche Namen zu verwenden, da sie oft kürzer sind, man könnte die Funktion auch "finde_klammergegenstück" nennen.
cnt beginnt bei 1, da es sich bei ausdruck[index] sicher um eine Klammer handelt und diese Klammer beim suchen des Gegenstücks nicht mehr geprüft werden muss. Darum beginnen die Forschleifen immer bei index+1 wenn es sich um eine öffnende Klammer handelt und nach der dazugehörenden schliessenden Klammer gesucht wird, bzw. bei index-1, wenn sich an Position index eine schliessende Klammer befindet und nach der dazugehörigen öffnenden klammer gesucht wird.
Die Funktion find_parenthesis(ausdruck, index) dient einzig und allein dazu, in einem Ausdruck mit Klammern das Gegenstück zur Klammer, die sich an Position "index" befindet zu finden.
Ich hab noch schnell ein Testprogramm für find_parenthesis gemacht.

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
def find_parenthesis(ausdruck, index):
    cnt = 1 # Zähler für Klammern
    if ausdruck[index] == "(":
        for i in xrange(index+1, len(ausdruck)):
            if ausdruck[i] == "(":
                cnt += 1
            elif ausdruck[i] == ")":
                cnt -= 1
            if cnt == 0: # schliessende Klammer gefunden
                break # fertig, i enthält den Index
    elif ausdruck[index] == ")":
        for i in xrange(index-1, -1,-1):
            if ausdruck[i] == ")":
                cnt += 1
            elif ausdruck[i] == "(":
                cnt -= 1
            if cnt == 0: # öffnende Klammer gefunden
                break # fertig, i enthält den Index
    if cnt != 0:
        raise ValueError("unbalanced parentesis")
    return i

if __name__ == "__main__":
    
    import sys
    
    while 1:
        ausdruck = raw_input("Ausdruck: ")
        if ausdruck == "":
            sys.exit()
        index = input("Klammer an Position: ")
        
        if ausdruck[index] not in ["(",")"]:
            print "Keine Klammer an Position %d" % index
            continue
        print find_parenthesis(ausdruck, index)
Gib zuerst einen Ausdruck ein mit beliebig verschachtelten Klammern,
dann den Index einer Klammer im Ausdruck.

Code: Alles auswählen

:~/Python/pythonforum$ python ausdruck.py
Ausdruck: 3*(4+(2-(3+5))*6)
Klammer an Position: 2
16
Ausdruck: 3*(4+(2-(3+5))*6)
Klammer an Position: 8
12
Ausdruck: 3*(4+(2-(3+5))*6)
Klammer an Position: 13
5
Die Zählung für die Position beginnt bei 0. Daher ist die 1. Klammer an Position 3

Im Hauptprogramm, beim Analysieren des Ausdrucks, wird dann immer, wenn der Parser auf eine Klammer stösst, die Funktion verwendet, um den ganzen geklammerten Ausdruck zu bekommen, bzw. zu überspringen.
Was jetzt innerhalb der Klammern steht, ausser weiterer Klammern, ist der Funktion total egal.

Ich würde Dir empfehlen, die Punkt vor Strich Regel gleich zu beachten. Erstens ist sie viel leichter zu implementieren, wenn du es von vorne herein berücksichtigst, als sie nachträglich einzubauen. Und Zweitens wird jeder, der eines Deiner Programme verwendet, welches dann die Eingabe eines Ausdrucks z.B in einem Eingabefeld für einen Integerwert mittels Deines Moduls ermöglicht, Punkt vor Strich voraussetzen und sonst seltsame Ergebnisse erhalten.

Aber erstmal musst Du das mit den Klammern auf die Reihe bekommen, sonst hats echt keinen Sinn.
Immer einen Schritt nach dem anderen machen, sonst wirds nix.

noch schnell zu 2.:
das könntest einfach in einer Pythonconsole ausprobieren:

Code: Alles auswählen

>>> index = 10
>>> for i in xrange(index-1, -1,-1):
>>>     print i
Gruß


Dookie

geklammerte ausdrücke

Verfasst: Freitag 2. April 2004, 14:12
von TripleH
Hi,

Danke Dookie für deine Hilfe.
Ja die Funktion war mir eigentlich im groben ganz klar aber jetzt hab ich sie noch besser verstanden.

gut eingabe ist der Ausdruck und der index an dem sich eine Klammer befindet.

Zurst lese ich den Ausruck ein entferne die Leerzeichen und überprüfe ob der Ausdruck mit ner klammer beginnt und endet und kann die ja dann einfach löschen da sie nicht weiter relevant sind.

So wenn wir dann doch Punkt vor strich Rechnung beachten hab ich flogenden Vorschlag.


Angefangen hab ich mit der Suche nach einer Summe.

o Summe besteht aus einem Produkt, gefolgt von beliebig vielen (auch null) Wiederholungen von + oder - und wieder einem Produkt.
Die Suche nach einer Summe sucht also erst mal ein Produkt und schaut dann ob ein Rechenzeichen + oder - kommt.

o Produkt besteht aus einer Potenz, gefolgt von beliebig vielen Paaren aus * oder / und wieder einem Produkt.
Also erst mal eine Potenz erkennen, dann schauen ob * oder / kommt und dann wieder nach einer Potenz suchen.

o eine Potenz besteht aus einem Ausdruck (oder wie du das nennen willst), evtl. gefolgt von ** und wieder einem Ausdruck.

Ein Ausdruck ist entweder eine Zahl, oder etwas in Klammern. Bei einer Klammer fang ich wieder von vorne an und suche eine Summe.

Dann müsste das so etwa funktionieren:
1+2*3
Ich suche erst nach einer Summe. Die Summe sucht nach einem Produkt, das sucht eine Potenz und die gibt "1" zurück, bis zurück zur Suche nach Summe. Die erkennt jetzt ein + und sucht wieder nach einem Produkt, das Produkt bekommt eine 2 zurück und erkennt das *. Daraufhin sucht es weiter und bekommt die 3 als Zahl. Es berechnet 2*3 und erkennt dass nichts produktmäßiges mehr kommt, daher übergibt es 6 an die Summe. Diese 6 ist jetzt der zweite Summand für die Summe, sie kann jetzt 1+6 berechnen.

Mit Klammern wäre es so: (1+2)*3
Hier wieder Suche nach Summe, die sucht erst mal ein Produkt, das sucht eine Potenz und die erkennt "(". Daraufhin wird von vorne angefangen, bis 1+2 erkannt und berechnet ist. Diese 3 wandert in der Rekursion zurück bis zur Produktsuche, denn die Produktsuche erkennt das * und sucht daraufhin wieder weiter.

So aber das ist wohl nicht ganz wie du es im Sinn hast aufgrund deiner Erfahrung oder? Da die gleichen Teile wieder und wieder geparst werden.

klar ist das Ausdrücke innerhalb einer klammer Priorität haben.

Doch wie nutz ich die Funktion find_parenthesis?
geh ich mit ner laufvariablen von links los und wenn nen öffnende Klammer kommt übergb ich die Position und die Funktion liefert mir die stelle zurück wo sich dasgegenstück befindet. Allerdings können dann ja immer noch klammer in der klammer sein die berücksichtigt werden müssen da höhere Priorität oder?

Ich weiß sind wieder nen par dummer Fragen bestimmt aber man lernt ja gern dazu.

MFG

Verfasst: Freitag 2. April 2004, 21:15
von Dookie
Hi auch,

so dumm sind Deine Fragen gar nicht. Ich bin sicher, viele hier im Forum haben die gleichen Fragen und harren der Antworten.

Erstmal legen wir die Begriffe fest.
Ein Operator ist "+", "-", "*", "/" oder "**"

Ein Ausdruck ist entweder eine Zahl, oder beliebig viele Ausdrücke, die auch in Klammern stehen können, die durch jeweils einen Operator getrennt sind.

Der obige Satz, enthält in der Erklärung wieder das Substantiv (Ausdruck).
Hier ist schon die Recursion zu erahnen, die uns später beim Aufbau des Rechenbaumes wieder begegnen wird.

Dein Ansatz ist zwar naheliegend, aber das, für den Menschen, naheliegende ist nicht immer ideal wenns ein Computer machen muss.
Schauen wir uns mal einen recht komplexen Ausdruck an.

Code: Alles auswählen

3+4-(5+5*(2+3)-6*(3+8)-7)*9
wie würdest Du von hand einen solchen Ausdruck berechnen?
sicher, indem du den Ausdruck zerlegst. Als Mensch siehtst Du auf einen Blick, daß du die erste Rechnung 3+4 gleich ausrechnen kannst, weil danach ein - kommt. auch können die innersten Klammern 2+3 und 3+8 gleich ausgerechnet werden. Das ergibt dann den neuen Ausdruck:

Code: Alles auswählen

7-(5+5*5-6*11-7)*9
jetzt kann der Ausdruck in der Klammer betrachtet werden, und hier die Multiplikationen ausgeführt werden.

Code: Alles auswählen

7-(5+25-66-7)*9
bleibt dann noch übrig.
jetzt kann der Ausdruck in der klammer einfach ausgerechnet werden.

Code: Alles auswählen

7--43*9
noch die letzte Multiplikation

Code: Alles auswählen

7--387
wenn wir das jetzt noch ausrechnen bekommen wir 394 als Ergebnis.

Nun ist ein Computer aber kein Mensch, Der Computer arbeitet im Gegensatz zum Gehirn, welches die Daten parallel verarbeitet, streng linear. Also immer eins nach dem anderen.
Allerdings haben wir eines schon beim rechenen "wie ein Mensch" gesehen, jeder beliebig komplexe Ausdruck lässt sich in einfachere Ausdrücke zerlegen, die dann mit den Operatoren (+-*/**) verbunden sind.

Frech wie wir sind klauen wir mal beim alten Cäsar, der schon gesagt haben soll "Divide et impera!" - was meisst mit "Teile und herrsche" übersetzt wird.
Da sich ein Ausdruck aus Ausdrücken zusammensetzt (ausser er besteht aus einer einzelen Zahl) können wir ihn aufteilen und die resultierenden Teile wieder als Ausdrücke bearbeiten, also wieder aufteilen, und so weiter, bis wir bei lauter einzelnen Zahlen und Operatoren sind.

Vorher müssen wir uns noch überlgen, wie wir die Operatoren (+,-,*,/,**) mit Prioritäten versehen können, um gleich "Punkt vor Strich" zu berücksichtigen. Am einfachsten legen wir uns ein Dictionary an, das die Operatoren als Schlüssel verwendet und jeder Operator bekommt als Wert eine Priorität.

Code: Alles auswählen

op_pri = {"+" : 0, "-" : 0, "*" : 1, "/" : 1, "**" : 2}
Man könnte sagen "Je höher die Priorität, desto 'enger' werden die Ausdrücke durch den Operator aneinander gebunden". Also umso früher müssen die Ausdrücke die Durch den Operator getrennt sind berechnet werden. Bevor die Ausdrücke mit niedrigerer Priorität an die Reihe kommen.
Operatoren mit gleicher Priorität und auf gleicher Klammerebene, werden in der Reihenfolge des Auftretens im Ausdruck berechnet, also der am weitesten links stehende zuerst.

Intuitiv warst Du bei Deinem Beispiel schon auf der richtigen Fährte. Um einen gegebenen Ausdruck aufzuteilen, suchen wir eben nicht, den Operator mit der höchsten Priorität, sonder den mit der niedrigsten, und erhalten so einen linken Ausdruck, den Operator, und einen rechten Ausdruck. Aus "1+2*3" wird so "1"+"2*3".

Wenn wir jetzt unseren Rechenbaum aufbauen, erstellen wir einen Knoten, dieser enthält dann als self.value das "+", und für den linken zweig, wird ein Knoten erstellt, der dann als self.value die "1" enthält, und für den rechten Zweig einen Knoten der aus dem rechten Teilausdruck "2*3" seine Daten bezieht.
Also die Init-Methode unserer Rechenbaumknoten, bekommt einen Ausdruck, parst und, wenn es sich nicht um eine einzelne Zahl handelt, zerlegt sie den Ausdruck, beim Operator mit der kleinsten Priorität, und erstellt sich für den linken und rechten Ast weitere Knoten.

Hier mal der ganze Code zur Berechnung von Ausdrücken mittels Rechenbaum.

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

op_pri = {"+" : 0, "-" : 0, "*" : 1, "/" : 1, "**" : 2}

def find_parenthesis(ausdruck, index):
    cnt = 1 # Zähler für Klammern
    if ausdruck[index] == "(":
        for i in xrange(index+1, len(ausdruck)):
            if ausdruck[i] == "(":
                cnt += 1
            elif ausdruck[i] == ")":
                cnt -= 1
            if cnt == 0: # schliessende Klammer gefunden
                break # fertig, i enthält den Index
    elif ausdruck[index] == ")":
        for i in xrange(index-1, -1,-1):
            if ausdruck[i] == ")":
                cnt += 1
            elif ausdruck[i] == "(":
                cnt -= 1
            if cnt == 0: # öffnende Klammer gefunden
                break # fertig, i enthält den Index
    if cnt != 0:
        raise ValueError("unbalanced parentesis")
    return i

def parse(ausdruck):
    op = "" # wir haben noch keinen Operator
    op_at = -1
    if ausdruck[0] in "+-":
        i = 1 # zeichen an position 0 ist nur ein Vorzeichen
    else:
        i = 0
    while i < len(ausdruck):
        # Wenn eine Klammer, dann überspringen.
        if ausdruck[i] == "(":
            i = find_parenthesis(ausdruck, i)+1
            if i >= len(ausdruck):
                break
        if ausdruck[i] in "+-*/": # Operator gefunden
            if ausdruck[i:i+2] == "**": # Potenz behandeln
                found = "**"
            else: # normaler ein-zeichen Operator
                found = ausdruck[i]
            if op: # wir hatten schon einen Operator gefunden
                # wenn priorität des neuen Operators <= dem Alten
                if op_pri[found] <= op_pri[op]:
                    op = found # neuer Operator hat kleinere Priorität
                    op_at = i # also nehmen wir den
            else:
                op = found # unser erster gefundener operator
                op_at = i
            i += len(found) # wegen '**' sonst würde 1 statt len(found) genügen
            if ausdruck[i] in "+-": # Eventuelles vorzeichen der nächsten Zahl
                i += 1     # überspringen
        else: # kein Operator
            i += 1 # gehe zum nächsten zeichen
    if op_at >= 0:
        # Operator und linken und rechten Ausdruck zurückgeben.
        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):
        # falls ganzer Ausdruck geklammert, klammern entfernen
        while (ausdruck[0] == "(" and
               find_parenthesis(ausdruck, 0) == len(ausdruck)-1):
            ausdruck = ausdruck[1:-1]
            
        try: # versuche ob 'ausdruck' eine Zahl darstellt
            self.data = int(ausdruck)
            self.left = None
            self.right = None
        except ValueError: # 'ausdruck' ist keine Zahl!
            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 == "/":
                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()
        rechenBaum = Node(ausdruck)
        print "Rechenbaum:"
        rechenBaum.print_me()
        print "Ergebnis:", rechenBaum.GetValue()
Ich denke, damit hast du ersmal ne weile zu tun beim Testen und rumspielen. Wenn Du glaubst, das Prinzip verstanden zu haben, kannst Du ja versuchen das Programm um die module-Operation "%" welche den ganzzahligen Rest einer Division liefert zu ergänzen.



Gruß

Dookie

P.S.: Du hast Glück, daß ich vor kurzem ein ähnliches Modul erstellt habe, so brauchte ich nur die relevanten Teile zu kopieren und auf int statt float umzustricken.

geklammerte ausdrücke

Verfasst: Sonntag 4. April 2004, 18:24
von TripleH
hi,

danke dookie für deine Hilfe. Ich hab wirklich das ganze we rumgespielt um das Progarmm zu vertehen und hab noch nen par kleinigkeiten verändert.

Ich hab auch an dem Problem mit der ganzzahligen Division gearbeitet.
Meiner Meinung nach müßte ich doch an dieser Stelle hier eingreifen:

Code: Alles auswählen

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
                    return self.left.GetValue() / self.right.GetValue()
                else:
                    return "Keine ganzzahlige Division" 
            elif self.data == "**": 
                return self.left.GetValue() ** self.right.GetValue() 
            else: 
                return "Fehler: unbekannter Operand %s" % self.data
allerdings kommt dann nen sytanxfehler.
Ich überlg schon die ganze Zeit. Eigentlich kanns sich doch nur um ne Kleinigkeit handeln die ich überseh oder?

Noch einen schönen Abend.
MFG

Verfasst: Sonntag 4. April 2004, 19:46
von Dookie
Hallo,

uups da is mir doch nen kleiner "schönheitsfehler" passiert.
Bei der Abfrage nach dem Multiplikationsoperator sollte es natürlich auch elif und nicht nur if heissen.

Code: Alles auswählen

    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()
            elif self.data == "*": # HIER ÄNDERN !!!
                return self.left.GetValue() * self.right.GetValue()
            elif self.data == "/":
                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
Du hast schlicht und einfach einen : am Ende der Zeile beim if vergessen.

Code: Alles auswählen

if self.left.GetValue() % self.right.GetValue() == 0:
Der Interpreter gibt dann bei der Fehlermeldung die nächste Zeile als Fehlerursache an, aber der Fehler liegt eine Zeile höher. Da fällt jeder am Anfang drauf rein, aber nach dem dritten Mal hat mans raus :D

Hmm das mit Deiner Änderung, wegen der Ganzzahldivision versteh ich jetzt nicht ganz. Da Du ja nur mit Ganzzahlen arbeitest, ist natürlich z.B. 13/2 = 6 ich würde das aber gar nicht ändern, da es ja bei ganzen Zahlen so üblich ist. Ausserdem bringst Du den ganzen Rechenbaum zum zusammenbrechen, wenn du da statt des Integers einen String zurückgibst.
Du könntest dort mit einer Warnung arbeiten, die einen Hinweis ausgibt, daß bei der Division ein Rundungsfehler auftritt.

Code: Alles auswählen

    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()
            elif self.data == "*": # HIER ÄNDERN !!!
                return self.left.GetValue() * self.right.GetValue()
            elif self.data == "/":
                from warnings import warn
                l = self.left.GetValue()
                r = self.right.GetValue()
                if l % r != 0:
                    warn("Divisionswarnung: %i / %i hat kein exaktes Resultat!" % (l,r))
                return l / r
            elif self.data == "**":
                return self.left.GetValue() ** self.right.GetValue()
            else:
                return "Fehler: unbekannter Operand %s" % self.data

Gruß


Dookie

geklammerte ausdrücke

Verfasst: Sonntag 4. April 2004, 20:44
von Calanetics
Hi,

oh schön das hier über dieses Thema so konstruktiv geredet wird.
Ich versuch das gleiche Problem gerade in Delphi zu lösen.
Ich hoff mir kann noch jemand helfen bei der Interpretation deines Programms Dookie.

Die Funktion find_parenthesis ist klar geworden.
Die Funktion parse soweit auch.
Doch bei ihr wird der Operator der linke und der rechte Ausdruck zurückgegeben.Operator ist der mit der kleinsten Priorität.

Bei der klasse Node ist mir noch nicht ganz klar. Und zwar bei der Funktion def __init__(self, ausdruck): wird doch nur der ausdruck übergeben eigentlich.Was bedeutet denn das self?
Dann wird zuerst die äußerste Klammer gelöscht falls vorhanden.

doch wie kann jetzt mit self.data auf den ausdruck zugegriffen werden und das self.left und self.right ist mir auch noch nicht ganz klar.

Grundsätzlich wird geprüft ob der ausdruck nur ne Zahl ist und ansonsten wird geparst.data wird dann der operator zugewiesen und left die linke seite und right der rechte.

doch diese 3 zeilen sind mir dann nicht ganz klar.
self.data = data
self.left = Node(left)
self.right = Node(right)

Praktisch wird ja in der Klasse der suchbaum aufgebaut oder?
Doch wie stell ich mir das an nem Beispiel vor orientiert am Quelltext?
erst an nem leichten und an nem schwierigeren.

leicht:

3*3+4

zuerst wird dann bei der parse funktion +,3*3,4 zurückgegeben.untersucht werden musste doch dann aber noch der Ausdruck 3*3 doch wo wird denn rekursiv aufgerufen denn die parse Funtion geht den Ausdruch doch nur einmal durch?
schwerer Ausdruck.

4*4+3*(3*3)

so beim ersten durchlauf wird wieder zurücgegeben +,4*4,3*(3*3)

Doch wie gehts dann weiter theoretisch anhand des Quelltextes?

Die Funktion getValue ist ja dann nur zusammenrechnen des suchbaumes oder?
Ich hoff ihr könnt noch nen bißchen helfen auf meinen vielen Fragen.

mfg

lara

Re: geklammerte ausdrücke

Verfasst: Montag 5. April 2004, 00:39
von Dookie
Calanetics hat geschrieben:Hi,
Hi auch,
oh schön das hier über dieses Thema so konstruktiv geredet wird.
Ich versuch das gleiche Problem gerade in Delphi zu lösen.
Ich hoff mir kann noch jemand helfen bei der Interpretation deines Programms Dookie.
Das mach ich doch glatt selber ;)
Die Funktion find_parenthesis ist klar geworden.
Die Funktion parse soweit auch.
Doch bei ihr wird der Operator der linke und der rechte Ausdruck zurückgegeben.Operator ist der mit der kleinsten Priorität.
Yepp so ist es
Bei der klasse Node ist mir noch nicht ganz klar. Und zwar bei der Funktion def __init__(self, ausdruck): wird doch nur der ausdruck übergeben eigentlich.Was bedeutet denn das self?
Das ist etwas Pythontypisches. Das self ist die Referenz auf die Instanz der Klasse Node, welche mit der Methode __init__(...) initialisiert wird.
Also bei der Zeile rechenBaum = Node(ausdruck) wird die Methode __init__(self, ausdruck) von Node aufgerufen, wobei die neue Instanz, welche nach der Initialisierung, an rechenBaum zugewiesen wird, implizit als erstes Argument an die Methode übergeben.
Das ist so ähnlich, als wenn Du ein Programm mit Argumenten aufrufst, dann hast Du in argv[0] ja auch den Namen des Programms und erst danach folgen die Parameter, die beim Start mitgegeben wurden.
Dann wird zuerst die äußerste Klammer gelöscht falls vorhanden.

doch wie kann jetzt mit self.data auf den ausdruck zugegriffen werden und das self.left und self.right ist mir auch noch nicht ganz klar.
mit self.data kann gar nicht auf den Ausdruck zugegriffen werden. self.data enthält entweder einen Integerwert, oder aber einen String mit dem Operator.
Grundsätzlich wird geprüft ob der ausdruck nur ne Zahl ist und ansonsten wird geparst.data wird dann der operator zugewiesen und left die linke seite und right der rechte.
Ja so ist es.
doch diese 3 zeilen sind mir dann nicht ganz klar.
self.data = data
self.left = Node(left)
self.right = Node(right)

Praktisch wird ja in der Klasse der suchbaum aufgebaut oder?
Genau, da wird der Rechenbaum aufgebaut, gesucht wird da nix, das kommt erst zu Ostern ;)
Doch wie stell ich mir das an nem Beispiel vor orientiert am Quelltext?
Uii, da hat der Osterhase aber schon zugeschlagen und die Recursion im Dschungel des Pythoncodes versteckt ;)
erst an nem leichten und an nem schwierigeren.

leicht:

3*3+4

zuerst wird dann bei der parse funktion +,3*3,4 zurückgegeben.untersucht werden musste doch dann aber noch der Ausdruck 3*3 doch wo wird denn rekursiv aufgerufen denn die parse Funtion geht den Ausdruch doch nur einmal durch?
Ja, danach wird dann das Ergebnis des Parsens, also der Operator und der linke und der rechte Teilausdruck verwendet um den Baum aufzubauen.
Das geschieht hier:

Code: Alles auswählen

            data, left, right = parse(ausdruck)
            self.data = data # Operator an self.data zuweisen
            self.left = Node(left) # Baum links erweitern
            self.right = Node(right) # Baum rechts erweitern
bei self.left = Node(left) wird ein neuer Knoten mit dem Ausdruck 3*3 erzeugt dadurch wird wieder __init__(self, ausdruck) der Klasse Node aufgerufen mit der neuen Instanz, die an self.left zugewiesen werden soll als ersten und dem Ausdruck 3*3 als zweiten Parameter. Dabei der Ausdruck 3*3 geparst und zerlegt.
schwerer Ausdruck.

4*4+3*(3*3)

so beim ersten durchlauf wird wieder zurücgegeben +,4*4,3*(3*3)

Doch wie gehts dann weiter theoretisch anhand des Quelltextes?
Praktisch wie beim einfachen Ausdruck.
ich hab hier mal eine abgewandelte Version der __init__ Methode von Node, welche zusätzliche Ausgaben auf den Bildschirm bringt.

Code: Alles auswählen

    def __init__(self, ausdruck, depth=0):
        print "-"*depth, ausdruck
        # falls ganzer Ausdruck geklammert, klammern entfernen
        while (ausdruck[0] == "(" and
               find_parenthesis(ausdruck, 0) == len(ausdruck)-1):
            ausdruck = ausdruck[1:-1]
            
        try: # versuche ob 'ausdruck' eine Zahl darstellt
            self.data = int(ausdruck)
            self.left = None
            self.right = None
        except ValueError: # 'ausdruck' ist keine Zahl!
            data, left, right = parse(ausdruck)
            self.data = data
            self.left = Node(left, depth+1)
            print " "*depth, data
            self.right = Node(right, depth+1)
Die Ausgabe deines schweren Ausdrucks schaut dann so aus:

Code: Alles auswählen

Ausdruck: 4*4+3*(3*3)
 4*4+3*(3*3) # erster Aufruf von __init__ der Ausdruck wird am + zerlegt
- 4*4       # zweiter Aufruf von __init__ mit linkem teilbaum wird am * zerlegt
-- 4        # dritter Aufruf von __init__ 4 ist ein int und braucht nicht zerlegt werden
  *         # der linke teil von 4*4 ist fertig
-- 4        # vierter Aufruf von __init__ ausdruck enthält nur "4" also als int merken.
 +           # der linke ausdruck vor dem + ist fertig zerlegt
- 3*(3*3)   # fünfter Aufruf von __init__ rechter teilausdruck wird zerlegt
-- 3        # sechster Aufruf von __init__ eine 3
  *         # linker unterteilausdruck nach dem + und vor dem * ist fertig
-- (3*3)    # siebter Aufruf von __init__ 3*3 in klammern wird nun zerlegt
--- 3       # achter Aufruf von __init__ ausdruck enthält nur "3" also fertig
   *        # linker teil des unterunterausdrucks fertig
--- 3       # letzter Aufruf von __init__  jetzt gibts nichts mehr zu zerlegen
Du siehst, __init__(self, ausdruck) wird für jeden Teil des Ausdrucks aufgerufen. Die "-" zeigen dabei die Recursionstiefe an.
Die Funktion getValue ist ja dann nur zusammenrechnen des suchbaumes oder?
Ja, bei getValue wird der Rechenbaum "postorder" durchlaufen, also quasi von den äusseren Knoten zur Wurzel "aufgelöst"
Ich hoff ihr könnt noch nen bißchen helfen auf meinen vielen Fragen.

mfg

lara
hoffentlich sind jetzt auch die letzten Klarheiten beseitigt ;)


Gruß

Dookie

geklammerte ausdrücke

Verfasst: Montag 5. April 2004, 12:18
von Calanetics
Hi,

Dank dir Dookie für die schnelle Hilfe und ich glaub du freust dich schon auf Ostern :lol:
Jetzt hab ich auf jeden Fall ne Grundlage um es mal in Delphi zu programmieren.

Allerdiings hab ich noch einen zusätzlichen Ansatz wo ich im Internet schon gesucht hab wie verrückt und schon eine Algorithmen Bücher gewälzt hab. und Zwar wie man einen Ausdruch in der Infix-Notation
in die Postfix Notation(umgekehrte polnische Notation) umwandelt.
Da du ja anscheinend schon Erfahrung hast mit diesem Thema hoffe das du weißt wie der theoretische Algorithmus ist.
Einezeln betrachtet ist das Problem klar.

Infix: 3 * ( ( 1 + 2 ) * 3 + 5)

Postfix: 3 1 2 + 3 * 5 + *

Der Operator steht hinter den Operanden.
Denk mal Teile kann man ja schon aus dem Programm zuvor übernehmen aber leider ist es schwer zu Programmieren wenn die Theorie noch nicht klar ist.
Ich hoff du hast schon mal was davon gehört und kannst mir helfen.

MFG

Lara

Verfasst: Montag 5. April 2004, 14:26
von Dookie
Null problemo.

das mit der Ausgabe als UPN ist sehr einfach. Bei meinem Beispiel wird ja auch der Rechenbaum angezeigt, ganz links ist die Wruzel, und rechts sind die Knoten. Je weiter rechts umso höher die Prioriät.
Wenn Der Baum in "postorder", also zuerst linker ast, dann rechter ast, dann der eigene wert in data zu einem String zusammengefügt werden, bekommst Du die "umgekehrte polnische Notation".

Code: Alles auswählen

    def upn(self):
        result = ""
        if self.left != None:
            result += self.left.upn()
        if self.right != None:
            result += self.right.upn()
        result += " "+str(self.data)
        return result
Füge das nach der Mehode GetValue als neue Methode in der Nodeklasse ein.
Das Hauptprogramm, nach dem if __name__ == "__main__" wird dann noch so angepasst.

Code: Alles auswählen

if __name__ == "__main__":
    
    import sys
    
    while 1:
        ausdruck = raw_input("Ausdruck: ")
        if ausdruck == "":
            sys.exit()
        ausdruck = ausdruck.strip().replace(" ","")
        rechenBaum = Node(ausdruck)
        print "Rechenbaum:"
        rechenBaum.print_me()
        print "UPN:", rechenBaum.upn()
        print "Ergebnis:", rechenBaum.GetValue()
Um einen Ausdruck in UPN auswerten zu können musste man die __init__ methode anpassen, eventuell um einen zusätzlichen Parameter erweitern, der angzeigt ob der Ausdruck als UPN oder als infix Ausdruck auszuwerden ist. Je nach dem wird dann eben eine neue Parserfunktion verwendet, bzw. bei UPN leicht möglich, der Ausdruck gleich in einen Baum überführt, was bei UPN viel einfacher geht als bei infix Notation. Ich werd mich heute abend mal an eine entsprechende Anpassung machen.


Gruß

Dookie

Verfasst: Montag 5. April 2004, 20:14
von Dookie
So ich habs jetzt um die umgekehrte polnische Notation erweitert.
Ich poste hier meinen aktuellen Code, erstens ists ja nicht sooo viel, und zweitens interessieren sich sicher nicht nur wir drei dafür.

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
"""
    Modul:          Rechenbaum.py
    Description:    Berechne ausdruck in infix und upn
    Version:        V1.0
    Copyright:      2003 by Fritz Cizmarov fritz(at)sol.at
    Created:        28. Mär. 2004
    Last modified:  05. Apr. 2004
    License:        free
    Requirements:   Python2.3
"""

op_pri = {"+" : 0, "-" : 0, "*" : 1, "/" : 1, "**" : 2}

def find_parenthesis(ausdruck, index):
    cnt = 1 # Zähler für Klammern
    if ausdruck[index] == "(":
        for i in xrange(index+1, len(ausdruck)):
            if ausdruck[i] == "(":
                cnt += 1
            elif ausdruck[i] == ")":
                cnt -= 1
            if cnt == 0: # schliessende Klammer gefunden
                break # fertig, i enthält den Index
    elif ausdruck[index] == ")":
        for i in xrange(index-1, -1,-1):
            if ausdruck[i] == ")":
                cnt += 1
            elif ausdruck[i] == "(":
                cnt -= 1
            if cnt == 0: # öffnende Klammer gefunden
                break # fertig, i enthält den Index
    if cnt != 0:
        raise ValueError("unbalanced parentesis")
    return i

def parse(ausdruck):
    op = "" # wir haben noch keinen Operator
    op_at = -1
    if ausdruck[0] in "+-":
        i = 1 # zeichen an position 0 ist nur ein Vorzeichen
    else:
        i = 0
    while i < len(ausdruck):
        # Wenn eine Klammer, dann überspringen.
        if ausdruck[i] == "(":
            i = find_parenthesis(ausdruck, i)+1
            if i >= len(ausdruck):
                break
        if ausdruck[i] in "+-*/": # Operator gefunden
            if ausdruck[i:i+2] == "**": # Potenz behandeln
                found = "**"
            else: # normaler ein-zeichen Operator
                found = ausdruck[i]
            if op: # wir hatten schon einen Operator gefunden
                # wenn priorität des neuen Operators <= dem Alten
                if op_pri[found] <= op_pri[op]:
                    op = found # neuer Operator hat kleinere Priorität
                    op_at = i # also nehmen wir den
            else:
                op = found # unser erster gefundener operator
                op_at = i
            i += len(found) # wegen '**' sonst würde 1 statt len(found) genügen
            if ausdruck[i] in "+-": # Eventuelles vorzeichen der nächsten Zahl
                i += 1     # überspringen
        else: # kein Operator
            i += 1 # gehe zum nächsten zeichen
    if op_at >= 0:
        # Operator und linken und rechten Ausdruck zurückgeben.
        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, upn=False):
        if upn: # Ausdruck ist in umgekehrter polnischer Notation
            if isinstance(ausdruck, basestring):
                ausdruck = ausdruck.split() # Ausdruck in Liste umwandeln
            last = ausdruck.pop() # letzten Operand/Operator holen
            try:
                self.data = int(last) # ist integer
                self.left = None
                self.right = None
            except ValueError: # ist Operator
                self.data = last # Operator speichern
                self.right = Node(ausdruck, True) # rechten Ast aufbauen
                self.left = Node(ausdruck, True) # linken Ast aufbauen
        else:
            # falls ganzer Ausdruck geklammert, Klammern entfernen
            while (ausdruck[0] == "(" and
                   find_parenthesis(ausdruck, 0) == len(ausdruck)-1):
                ausdruck = ausdruck[1:-1]
                
            try: # versuche ob 'ausdruck' eine Zahl darstellt
                self.data = int(ausdruck)
                self.left = None
                self.right = None
            except ValueError: # 'ausdruck' ist keine Zahl!
                data, left, right = parse(ausdruck)
                self.data = data
                self.left = Node(left)
                #print "."*depth, data
                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 == "/":
                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 upn(self):
        result = ""
        if self.left != None:
            result += self.left.upn()
        if self.right != None:
            result += self.right.upn()
        result += " "+str(self.data)
        return result
    
    def infix(self, parent=""):
        if type(self.data) is int:
            return str(self.data)
        else:
            if parent and op_pri[parent] > op_pri[self.data]:
                result = "(%s %s %s)" # ausdruck muss geklammert werden
            else:
                result = "%s %s %s" # ausdruck ohne Klammern
            return result % (self.left.infix(self.data),
                             self.data,
                             self.right.infix(self.data))
                
    def print_me(self, depth=0):
        indent = "  "*depth # Einrückung des Baumes
        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()
        ausdruck = ausdruck.strip()
        if ausdruck[-1] in "+-/*": # letztes Zeichen ein Operator
            rechenBaum = Node(ausdruck, upn=True) # dann ists UPN
        else: # nicht UPN
            ausdruck = ausdruck.replace(" ","") # Leerzeichen löschen
            rechenBaum = Node(ausdruck)
        print "Rechenbaum:"
        rechenBaum.print_me() # als Baum darstellen
        print "INFIX:", rechenBaum.infix() # als INFIX darstellen
        print "UPN:", rechenBaum.upn() # als UPN darstellen
        print "Ergebnis:", rechenBaum.GetValue()
        print
war echt einfacher als ich selber dachte.
Erweitert wurde die __init__ Methode der NodeKlasse. Die Methoden upn und infix sind neu. Der Schlussteil des Scripts für das Erkennen der Notation des eingegebenen Ausdrucks und die Ausgabe von INFIX und UPN sind dann noch dazugekomen


Gruß

Dookie

geklammerte ausdrücke

Verfasst: Donnerstag 15. April 2004, 15:11
von lara
Hallo endlich mal ein Forum wo man infos über dieses wohl anscheind oft vorkommende Thema findet.

Ich möcht gern sowas ähnliches in C programmieren.
Mit python kenn ich mich noch nicht so gut aus aber ähnlichkeiten sind ja vorhanden:)

Und zwar ist es bei mir spezieller. Und zwar möcht ich nicht Punkt vor Strichrechnung beachten sondern nur mittels Klammerung soll die Priorität festgelegt werden. Jeder Operation muss also von einer Klammer umgeben sein oder es erscheint eine Fehlermeldung.

Beispiel:

(4+4)+(4*4)
ist zulässig

(4+4)+4*4
ist nicht gültig

(4+4+5)+(4*4)
ist ungültig

bei deinem Programm muss ich eigentlich nur die parse Funktion ändern oder seh ich das falsch?
Um ein par Sachen die entfallen hab ich es schon gekürzt.

Code: Alles auswählen

def parse(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: 
         
        return op, ausdruck[:op_at], ausdruck[op_at+len(op):] 
    else: 
        print "Fehler beim parsen von %s" % ausdruck 
        return None, None, None
Allerdings kommt jetzt hier dann noch die abfrage das wenn ein Audruck mehr als 1 Operator in einer Klammer hat nen Fehler kommt oder?


Und ich hoff du kannst noch mal so nett sein mir bei ner anderen kleinen Sache auf die Sprünge zu helfen für mein Verständnis.
Und zwar in der Klasse Node wird der Rechenbaum erstellt.
Doch in welcher Datenstruktur? Du sagtest self.data, self.left und self.right
ist weder ein String noch ein Integer Wert.Doch was ist es dann?

Vorallem bei der Funktion getValue wird ja mit self.data gearbeitet zum zusammenrechnen. Muss es dafür denn aber nich ein Integer Wert sein?

Ich hoffe du kannst mir da helfen.

Schöne Grüße

Lara

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

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:

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

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
Alle Zeiten sind UTC+01:00
Seite 1 von 2

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de