Seite 1 von 1
Klammernpaare
Verfasst: Donnerstag 27. Januar 2011, 17:32
von 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?
Re: Klammernpaare
Verfasst: Donnerstag 27. Januar 2011, 18:18
von 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
Re: Klammernpaare
Verfasst: Donnerstag 27. Januar 2011, 18:34
von Xynon1
Ahhrr, danke !
|
dafür gibt es hier leider keinen Smile, wo ist dieses Vieh, was mit dem Kopf immer vor die Wand haut ?
Re: Klammernpaare
Verfasst: Donnerstag 27. Januar 2011, 19:16
von 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()
Re: Klammernpaare
Verfasst: Donnerstag 27. Januar 2011, 20:42
von 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
Re: Klammernpaare
Verfasst: Donnerstag 27. Januar 2011, 21:53
von 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 ?
Re: Klammernpaare
Verfasst: Freitag 28. Januar 2011, 13:06
von 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
Re: Klammernpaare
Verfasst: Freitag 28. Januar 2011, 19:08
von 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.
Re: Klammernpaare
Verfasst: Samstag 29. Januar 2011, 06:42
von 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
Re: Klammernpaare
Verfasst: Samstag 29. Januar 2011, 15:18
von derdon
Wie wäre es mit einem seperaten Thread in Showcase?
Re: Klammernpaare
Verfasst: Samstag 29. Januar 2011, 20:58
von Xynon1