2016-07-19 10 views
5

ho bisogno di estrarre stringhe da parentesi annidate in questo modo:stringa estratto tra parentesi nidificate

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

Risultato (Ordine non importa):

This is slim shady 
Hello from the other side 
Who 
What 

nota, la stringa potrebbe avere N parentesi, e saranno sempre valide, ma potrebbero essere o non essere annidate. Inoltre, la stringa non deve iniziare con una parentesi.

Le soluzioni che ho trovato in linea per un problema simile suggeriscono un'espressione regolare, ma non sono sicuro che funzionerà in questo caso.

Stavo pensando di attuare questo simile a come abbiamo controllare se una stringa ha tutte le parentesi validi:

Passeggiata attraverso la stringa. Se vediamo un [spingiamo il suo indice in pila, se vediamo un], abbiamo sottostringa da lì al punto corrente.

Tuttavia, dovremmo cancellare quella sottostringa dalla stringa originale in modo da non ottenerla come parte di una delle uscite. Quindi, invece di spingere solo spingendo l'indice nello stack, stavo pensando di creare una LinkedList mentre procediamo, e quando troviamo un [inseriamo quel Nodo nella LinkedList. Questo ci permetterà di eliminare facilmente la sottostringa dalla LinkedList.

Questo sarebbe un buon approccio o c'è una soluzione più pulita e conosciuta?

EDIT:

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

Dovrebbe restituire (Ordine non importa):

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

spazi bianchi non importa, questo è banale per rimuovere in seguito. Ciò che conta è essere in grado di distinguere i diversi contenuti all'interno delle parentesi. Separandoli in nuove righe o con un elenco di stringhe.

+0

Questa è una bella domanda difficile, voglio risolverlo utilizzando la ricorsione, ma che potrebbe essere un po 'difficile :) –

+0

andare avanti e provare them'all .. – Sundeep

+0

qual è il costrutto iniziale con le staffe? Solo una stringa come "astring =" [questo è [ciao [chi] [cosa] dall'altra parte] slim shady] "'? Se sì, perché non semplicemente astring.replace (']', '') ',' astring.replace ('[', '') 'e quindi' astring.split() '? –

risposta

5

Questo codice esegue la scansione del testo di carattere e spinge un vuoto list al stack per ogni apertura [ e si apre la l'ultima ha spinto list dallo stack per ogni chiusura ].

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))) 

Uscita;

(' 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

Impressionante, praticamente esattamente con quello che avevo in mente. Inoltre, molto pulito e intuitivo. – lorenzocastillo

5

questo può tranquillamente essere risolto utilizzando espressioni regolari:

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

Si prega di consultare il post aggiornato. Penso che il tuo codice si rompa. Non ho un computer con me ATM. Andando a dare un'occhiata quando posso. – lorenzocastillo

+0

@lorenzocastillo aggiornato. –

1

È possibile rappresentare le corrispondenze utilizzando una struttura ad albero.

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()) 

L'output di questo programma sarà:

partita: questo è Slim Shady
Partita: ciao dall'altra parte
partita: chi
partita: cosa

+0

Vedere il post aggiornato. Non produce il risultato corretto – lorenzocastillo

+0

@lorenzocastillo bad bounds per sottostringhe, l'ho corretto! – 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()) 

Questo dà o/p -

questo è sottile ombreggiato

ciao dall'altro lato

che cosa

+0

Questo non è un output valido: 'who' e' what' devono essere corrispondenze distinte – Rerito

Problemi correlati