2016-07-19 24 views
5

Ich brauche wie so Strings aus verschachtelten Klammern zu extrahieren:Extract String in verschachtelten Klammern

[ this is [ hello [ who ] [what ] from the other side ] slim shady ] 

Ergebnis (Reihenfolge spielt keine Rolle):

This is slim shady 
Hello from the other side 
Who 
What 

Hinweis könnte die Zeichenfolge haben N Klammern, und sie werden immer gültig sein, aber möglicherweise verschachtelt sein oder nicht. Außerdem muss die Zeichenfolge nicht mit einer Klammer beginnen.

Die Lösungen, die ich online zu einem ähnlichen Problem gefunden habe, schlagen eine Regex vor, aber ich bin nicht sicher, dass es in diesem Fall funktionieren wird.

ich dies der Umsetzung ähnlich wie dachte, wie wir, ob ein String überprüfen alle gültigen Klammern hat:

Spaziergang durch den String. Wenn wir a sehen [wir schieben seinen Index auf den Stapel, wenn wir a sehen], teilen wir uns von dort zum aktuellen Punkt.

Allerdings müssten wir diese Teilzeichenfolge aus der ursprünglichen Zeichenfolge löschen, damit wir sie nicht als Teil eines der Ausgaben erhalten. Anstatt also nur den Index in den Stapel zu schieben, dachte ich daran, eine LinkedList zu erstellen, und wenn wir einen [wir fügen diesen Knoten auf der LinkedList ein. Dies ermöglicht uns, die Teilzeichenfolge aus der LinkedList zu löschen.

Wäre dies ein guter Ansatz oder gibt es eine sauberere, bekannte Lösung?

EDIT:

'[ this is [ hello [ who ] [what ] from the other [side] ] slim shady ][oh my [g[a[w[d]]]]]' 

Sollte Rückkehr (Reihenfolge spielt keine Rolle):

this is slim shady 
hello from the other 
who 
what 
side 
oh my 
g 
a 
w 
d 

Weiß Räume sind nicht wichtig, dass trivial ist danach zu entfernen. Es kommt darauf an, die verschiedenen Inhalte innerhalb der Klammern unterscheiden zu können. Entweder durch Trennung in neue Zeilen oder durch eine Liste von Strings.

+0

Dies ist eine nette schwierige Frage, ich will es lösen Rekursion verwenden, aber das ist vielleicht ein wenig schwierig sein :) –

+0

voran gehen und versuchen them'all .. – Sundeep

+0

was ist das anfängliche Konstrukt mit den Klammern? Nur eine Zeichenfolge wie 'astring =" [das ist [Hallo [wer] [was] von der anderen Seite] schlank schattig] "'? Wenn ja, warum nicht einfach astring.replace (']', '') ',' astring.replace ('[', '') 'und dann' astring.split() '? –

Antwort

5

Dieser Code den Text von Zeichen durchsucht und schiebt einen leeren list auf den Stapel für jede Öffnung [ und öffnet die zuletzt geschoben list aus dem Stapel für jede Schließung ].

text = '[ this is [ hello [ who ] [what ] from the other side ] slim shady ]' 

def parse(text): 
    stack = [] 
    for char in text: 
     if char == '[': 
      #stack push 
      stack.append([]) 
     elif char == ']': 
      yield ''.join(stack.pop()) 
     else: 
      #stack peek 
      stack[-1].append(char) 

print(tuple(parse(text))) 

Ausgabe;

(' who ', 'what ', ' hello from the other side ', ' this is slim shady ') 
(' who ', 'what ', 'side', ' hello from the other ', ' this is slim shady ', 'd', 'w', 'a', 'g', 'oh my ') 
+0

Ehrfürchtig, ziemlich genau mit dem, was ich mir vorgestellt habe. Auch sehr sauber und intuitiv. – lorenzocastillo

5

ganz bequem Dies kann regex gelöst werden:

import re 

s= '[ this is [ hello [ who ] [what ] from the other [side] ] slim shady ][oh my [g[a[w[d]]]]]' 

result= [] 
pattern= r'\[([^[\]]*)\]' #regex pattern to find non-nested square brackets 
while '[' in s: #while brackets remain 
    result.extend(re.findall(pattern, s)) #find them all and add them to the list 
    s= re.sub(pattern, '', s) #then remove them 
result= filter(None, (t.strip() for t in result)) #strip whitespace and drop empty strings 

#result: ['who', 'what', 'side', 'd', 'hello from the other', 'w', 'this is slim shady', 'a', 'g', 'oh my'] 
+0

Bitte siehe aktualisierten Beitrag. Ich denke, dein Code bricht. Habe keinen Computer bei mir ATM. Ich werde es mir ansehen, wenn ich kann. – lorenzocastillo

+0

@lorenzocastillo Aktualisiert. –

1

Sie Ihre Spiele mit einer baumartigen Struktur darstellen können.

class BracketMatch: 
    def __init__(self, refstr, parent=None, start=-1, end=-1): 
     self.parent = parent 
     self.start = start 
     self.end = end 
     self.refstr = refstr 
     self.nested_matches = [] 
    def __str__(self): 
     cur_index = self.start+1 
     result = "" 
     if self.start == -1 or self.end == -1: 
      return "" 
     for child_match in self.nested_matches: 
      if child_match.start != -1 and child_match.end != -1: 
       result += self.refstr[cur_index:child_match.start] 
       cur_index = child_match.end + 1 
      else: 
       continue 
     result += self.refstr[cur_index:self.end] 
     return result 

# Main script 
haystack = '''[ this is [ hello [ who ] [what ] from the other side ] slim shady ]''' 
root = BracketMatch(haystack) 
cur_match = root 
for i in range(len(haystack)): 
    if '[' == haystack[i]: 
     new_match = BracketMatch(haystack, cur_match, i) 
     cur_match.nested_matches.append(new_match) 
     cur_match = new_match 
    elif ']' == haystack[i]: 
     cur_match.end = i 
     cur_match = cur_match.parent 
    else: 
     continue 
# Here we built the set of matches, now we must print them 
nodes_list = root.nested_matches 
# So we conduct a BFS to visit and print each match... 
while nodes_list != []: 
    node = nodes_list.pop(0) 
    nodes_list.extend(node.nested_matches) 
    print("Match: " + str(node).strip()) 

Die Ausgabe dieses Programms lautet:

Spiel: Das ist Slim Shady
Spiel: hallo von der anderen Seite
Spiel: die
Spiel: Was

+0

Siehe den aktualisierten Beitrag. Es liefert nicht das richtige Ergebnis – lorenzocastillo

+0

@lorenzocastillo schlechte Grenzen für Teilstrings, habe ich es korrigiert! – Rerito

1
a = '[ this is [ hello [ who ] [what ] from the other side ] slim shady ]' 
lvl = -1 
words = [] 
for i in a: 
    if i == '[' : 
     lvl += 1 
     words.append('') 
    elif i == ']' : 
     lvl -= 1 
    else: 
     words[lvl] += i 

for word in words: 
    print ' '.join(word.split()) 

Dies gibt o/p -

das ist Slim Shady

hallo von der anderen Seite

wer was

+0

Dies ist keine gültige Ausgabe: 'wer' und' was' müssen unterschiedliche Übereinstimmungen sein – Rerito

Verwandte Themen