Klammernpaare

[Xynon1]

Wie kann ich Klammernpaare aus einem String erkennen ?

Meine Idee war schlicht zu prüfen wo sich die nächste Klammer der anderen Art (also öffnende-schließende) zu suchen und dann im Teilstring zu testen oben eine passende Zahl öffnende und schließende existieren, wenn nicht soll die nächste Klammer gesucht werden. Und das halt solange bis die inneren Klammern auf eine gleich Anzahl beider Arten kommt.

Gibt es hier einen einfacheren Algorithmus oder schon eine fertige Methode in Python?

[EyDu]

Mal so auf die Schnelle:

Code: Alles auswählen

>>> data = "3*(2+3*(7-4)/5)+6*(5+3)"                                                                    
>>> stack = []                                                                                                       
>>> for index, char in enumerate(data):
...     if char=="(":                                                                                                
...         stack.append(index)                                                                                      
...     elif char==")":                                                                                              
...         print stack.pop(), index                                                                                 
...                                                                                                                  
7 11                                                                                                                 
2 14                                                                                                                 
18 22 

oder

Code: Alles auswählen

>>> data = "2*(3+4*a[3(4)]*{1+2})+<x*(a+b+c)>"
>>> opening = "([{<"                                                                                                 
>>> closing = ")]}>"                                                                                                 
>>> mapping = dict(zip(closing, opening))
>>> stack = []                                                                                                       
>>> for index, char in enumerate(data):                                                                              
...     if char in opening:
...         stack.append((index, char))                                                                              
...     elif char in closing:                                                                                        
...         begin, value = stack.pop()
...         if value != mapping[char]:
...             raise ValueError()
...         print begin, index
... 
10 12
8 13
15 19
2 20
25 31
22 32

[Xynon1]

Ahhrr, danke !
|
dafür gibt es hier leider keinen Smile, wo ist dieses Vieh, was mit dem Kopf immer vor die Wand haut ?

[Xynon1]

Ich will den Thread hier gleich mal nutzen, um auch zu zeigen wo ich diese kleine Klammer Erkennung gebraucht habe.

Ich hatte mich heute mal mit der esoterische Programmiersprache Brainfuck beschäftigt und dabei das gebastelt: http://www.python-forum.de/viewtopic.ph ... 62#p190662
Aber ich habe keinen Python Interpreter für diese Sprache gefunden, und da mir diese aber gefallen hat, wollte ich selber einen bauen. Ist ja auch nicht schwer, durch die sehr simple Syntax, nur muss mir, wie man oben sehen kann, Brainfuck ziemlich das Gehirn verknotet haben, also schaut mal bitte über den Quelltext drüber ob ich noch irgendwelche Fehler drin habe. Danke schon mal im voraus.

Code: Alles auswählen

#!/usr/bin/env python
from collections import defaultdict
import sys

class Brainfuck(object):
    
    def __init__(self, command="", text=""):
        self.command_index = 0
        self.command = command
        self.text = list(text)
        self.index = 0
        self.work = defaultdict(int)
        self.inter = {"," : self.get, "." : self.put, ">" : self.up,
                      "<" : self.down, "+" : self.add, "-" : self.sub,
                      "[" : self.right, "]" : self.left }
        self.opened_brackets = self._brackets()
        self.closed_brackets = self._brackets(True) 
    
    def _brackets(self, inverted=False):
        brackets = {}
        stack = []   
        for index, char in enumerate(self.command):
            if char == "[":
                stack.append(index)
            elif char == "]":
                if inverted:
                    brackets[index] = stack.pop()
                else:
                    brackets[stack.pop()] = index
        return brackets
        
    def run(self):
        while self.command_index < len(self.command):
            char = self.command[self.command_index]
            if char in self.inter:
                self.inter[char]()
            self.command_index += 1

    def get(self):
        self.work[self.index] = ord(self.text.pop(0)) \
                                if len(self.text) > 0 else 0
        
    def put(self):
        sys.stdout.write(chr(self.work[self.index]))

    def right(self):
        if self.work[self.index] == 0:
            self.command_index = self.opened_brackets(True)
            
    def left(self):
        if self.work[self.index] != 0:
            self.command_index = self.closed_brackets[self.command_index]

    def add(self):
        self.work[self.index] += 1

    def sub(self):
        self.work[self.index] -= 1
        
    def up(self):
        self.index += 1

    def down(self):
        self.index -= 1


if __name__ == "__main__":
    string = ",.,[>+[>+>+<<-]>>[<<+>>-]<[<<+>>-]<<.,]"
    text = "Hello World"

    Brainfuck(string, text).run()

[sma]

Brainfuck-Interpreter (und andere als esoterische Programmiersprachen getarnte Möchtegern-Turingmaschinen) verstecken sich allein in diesem Forum garantiert mehrere. Auch ich hatte vor einiger Zeit mal einen BF-Compiler gebaut, hier in der verbesserten Version von mitsuhiko: http://www.python-forum.de/viewtopic.ph ... 85#p102085

Dein Code wirkt im Vergleich dazu irgendwie viel mehr, auch wenn ich nicht den Finger auf eine schlechte Stelle legen kann. Vielleicht ist es einfache der Ansatz, das ganze als Klasse zu realisieren, wo jede Funktion eine eigene Methode ist.

Stefan

[Xynon1]

Ah, danke für den Link, ist auch ein schöner Ansatz.

Was die Größe angeht, ja Klasse wie immer wieder zu klobig, zudem ist bei euch die abarbeitung etwas anders. Ihr generiert ja Python Code (da spart man alein bei den Variablennamen und den Funktionen die ich drin habe Platz) und führt ihn am Ende aus. Ich lese einfach nur den String an den bestimmten Stellen und führ ihn aus.
Bei den Klammern generiert ihr eine while-Schleife, ich springe im String, was ja nochmal einigen Platzt frisst. Aber ich denke ich kann es trotzdem erstmal so lassen, oder gibt es noch irgendeinen Grund es nicht zu nutzen ?

[Xynon1]

So, jetzt ist auch noch ein Debugger dazu gekommen: http://www.python-forum.de/pastebin.php ... ght=python.

Wäre noch an verbesserungs Vorschlägen interessiert.
Edit: In der TaggedText Klasse fehlt unten am Ende der Funktion "selection_clear" der folgende Code

Code: Alles auswählen

self.config(state="normal")

[DaMutz]

Die 'right'-Methode hat einen Fehler:

Code: Alles auswählen

    def right(self):
        if self.work[self.index] == 0:
            self.command_index = self.opened_brackets(True)

Ausserdem ist der Variablename 'string' ist nicht so gut gewählt. Besser wäre wohl 'brainfuck_program' oder so.

[Xynon1]

Dank dir, muss ich wohl beim ändern übersehen haben, muss natürlich

Code: Alles auswählen

    def right(self):
        if self.work[self.index] == 0:
            self.command_index = self.opened_brackets[self.command_index]

heißen.
Ja string ist nicht günstig gewählt, war auch nur zum Testen, wird aber auch geändert.

Wie sieht es sonst so mit der Bedienung aus ? - sollte man daran etwas konfortabler gestalten

[derdon]

Wie wäre es mit einem seperaten Thread in Showcase?

[Xynon1]

Hast natürlich recht - http://www.python-forum.de/viewtopic.php?f=9&t=25375