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

geklammerte ausdrücke

Beitragvon lara » Mittwoch 21. April 2004, 13:21

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

Beitragvon Dookie » Mittwoch 21. April 2004, 18:28

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

geklammerte ausdrücke

Beitragvon lara » Dienstag 27. April 2004, 15:50

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

Beitragvon Dookie » Dienstag 27. April 2004, 16:05

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

geklammerte ausdrücke

Beitragvon lara » Dienstag 27. April 2004, 23:24

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

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

Beitragvon Dookie » Mittwoch 28. April 2004, 17:13

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* ;)
Calanetics
User
Beiträge: 19
Registriert: Donnerstag 23. Oktober 2003, 08:04
Kontaktdaten:

geklammerte ausdrücke

Beitragvon Calanetics » Sonntag 2. Mai 2004, 15:00

Hallo,

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

Gruß

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

Beitragvon Dookie » Sonntag 2. Mai 2004, 16:17

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

Wieder da.

Beitragvon Dookie » Dienstag 13. Juli 2004, 17:14

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


Gruß

Dookie

Code: Alles auswählen

#!/usr/bin/env python
import this

Wer ist online?

Mitglieder in diesem Forum: mollyman