Jak przeanalizować ciąg znaków i zwrócić zagnieżdżoną tablicę?

Question

Chcę funkcji Python, która pobiera ciąg znaków i zwraca tablicę, gdzie każdy element w tablicy jest albo znakiem, albo inną tablicą tego rodzaju. Zagnieżdżone tablice są oznaczone w łańcuchu wejściowym zaczynając od "(" i kończąc na ")".

Zatem funkcja będzie działać tak:

1) foo("abc") == ["a", "b", "c"] 
2) foo("a(b)c") == ["a", ["b"], "c"] 
3) foo("a(b(c))") == ["a", ["b", ["c"]]] 
4) foo("a(b(c)") == error: closing bracket is missing 
5) foo("a(b))c") == error: opening bracket is missing 
6) foo("a)b(c") == error: opening bracket is missing 

Uwaga: Wolałbym rozwiązanie, które jest czysto funkcjonalne.

Answer 1

def foo(s): 
    def foo_helper(level=0): 
     try: 
      token = next(tokens) 
     except StopIteration: 
      if level != 0: 
       raise Exception('missing closing paren') 
      else: 
       return [] 
     if token == ')': 
      if level == 0: 
       raise Exception('missing opening paren') 
      else: 
       return [] 
     elif token == '(': 
      return [foo_helper(level+1)] + foo_helper(level) 
     else: 
      return [token] + foo_helper(level) 
    tokens = iter(s) 
    return foo_helper() 

I

>>> foo('a((b(c))d)(e)') 
['a', [['b', ['c']], 'd'], ['e']] 

Answer 2

Proponuję dwa sposoby:

Program Albo własne recusive zejście parser jak here lub użyj pyparsing, coś

import pyparsing as pp 
expr = pp.Forward() 
expr << pp.Word(pp.alphas) + pp.Optional('(' + expr + ')') + pp.Optional(pp.Word(pp.alphas)) 

tutaj opisać rekurencyjnego wyrażenia jako ciąg alfa, która mogą być przeplatane za pomocą zbilansowanych nawiasów. Po sprawdzeniu tego przykładu dla wyjść zobaczysz, jak uzyskać pożądaną strukturę wyjściową (chociaż będzie to wymagało pewnych ulepszeń po twojej stronie i wymaga trochę nauki o pyparstwie).

pozdrowienia Markus

Answer 3

Rekurencja jest czymś bardzo potężne, że należy starać się wykorzystywać.

Oto mój kod:

    # encoding: utf-8 
    # Python33 

    def check(s): 
     cs = [c for c in s if c == '(' or c ==')'] 
     flag = 0 
     for c in cs: 
      if flag < 0: 
       return 'opening bracket is missing'   
      if c == '(': 
       flag += 1 
      else: 
       flag -= 1 
     if flag < 0: 
      return 'opening bracket is missing' 
     elif flag > 0: 
      return 'closing bracket is missing' 
     else: 
      return '' 

    def _foo(cs): 
     result = [] 
     while len(cs): 
      c = cs.pop(0) 
      if c == '(': 
       result.append(_foo(cs)) 
      elif c == ')': 
       return result 
      else: 
       result.append(c) 
     return result 

    def foo(s): 
     valiad = check(s) 
     if valiad: 
      return valiad 
     cs = list(s) 
     return _foo(cs) 

    if __name__ == '__main__': 
     ss = ["abc","a(b)c","a(b(c))","a(b(c)","a(b))c","a)b(c"] 
     for s in ss: 
      print(foo(s)) 

Answer 4

One raczej szybkie i paskudne podejście (po prostu czegoś innego):

import json, re 

def foo(x): 
    # Split continuous strings 
    # Match consecutive characters 
    matches = re.findall('[a-z]{2,}', x) 
    for m in matches: 
     # Join with "," 
     x = x.replace(m, '","'.join(y for y in list(m))) 

    # Turn curvy brackets into square brackets 
    x = x.replace(')', '"],"') 
    x = x.replace('(', '",["') 

    # Wrap whole string with square brackets 
    x = '["'+x+'"]' 

    # Remove empty entries 
    x = x.replace('"",', '') 
    x = x.replace(',""', '') 

    try: 
     # Load with JSON 
     return json.loads(x) 
    except: 
     # TODO determine error type 
     return "error" 

def main(): 
    print foo("abc")  # ['a', 'b', 'c'] 
    print foo("a(b)c") # ['a', ['b'], 'c'] 
    print foo("a(b(c))") # ['a', ['b', ['c']]] 
    print foo("a(b))c") # error 

    print foo('a((b(c))d)(e)') # ['a', [['b', ['c']], 'd'], ['e']] 

Answer 5

iteracyjna.

def foo(xs): 
    stack = [[]] 
    for x in xs: 
     if x == '(': 
      stack[-1].append([]) 
      stack.append(stack[-1][-1]) 
     elif x == ')': 
      stack.pop() 
      if not stack: 
       return 'error: opening bracket is missing' 
       #raise ValueError('error: opening bracket is missing') 
     else: 
      stack[-1].append(x) 
    if len(stack) > 1: 
     return 'error: closing bracket is missing' 
     #raise ValueError('error: closing bracket is missing') 
    return stack.pop() 

assert foo("abc") == ["a", "b", "c"] 
assert foo("a(b)c") == ["a", ["b"], "c"] 
assert foo("a(b(c))") == ["a", ["b", ["c"]]] 
assert foo("a((b(c))d)(e)") == ['a', [['b', ['c']], 'd'], ['e']] 
assert foo("a(b(c)") == "error: closing bracket is missing" 
assert foo("a(b))c") == "error: opening bracket is missing" 
assert foo("a)b(c") == 'error: opening bracket is missing' 

Answer 6

def parse_nested(iterator, level=0): 
    result = [] 
    for c in iterator: 
     if c == '(': 
      result.append(parse_nested(iterator, level+1)) 
     elif c == ')': 
      if level: 
       return result 
      else: 
       raise ValueError("Opening parenthesis missing") 
     else: 
      result.append(c) 
    if level: 
     raise ValueError("Closing parenthesis missing") 
    else: 
     return result 

print parse_nested(iter('a((b(c))d)(e)'))  

Answer 7

Korzystanie regex i ast.literal_eval

>>> import re 
>>> from ast import literal_eval 
>>> def listit(t): 
...   return list(map(listit, t)) if isinstance(t, (list, tuple)) else t 
... 
def solve(strs): 
    s = re.sub(r'[A-Za-z]', "'\g<0>',", strs) 
    s = re.sub(r"\)", "\g<0>,", s) 
    try: return listit(literal_eval('[' + s + ']')) 
    except : return "Invalid string! " 
...  
>>> solve("abc") 
['a', 'b', 'c'] 
>>> solve("a(b)c") 
['a', ['b'], 'c'] 
>>> solve("a(b(c))") 
['a', ['b', ['c']]] 
>>> solve("a(b(c)") 
'Invalid string! ' 
>>> solve("a)b(c") 
'Invalid string! ' 
>>> solve("a(b))c") 
'Invalid string! ' 
>>> solve('a((b(c))d)(e)') 
['a', [['b', ['c']], 'd'], ['e']]