Cách phân tích cú pháp một chuỗi và trả về một mảng lồng nhau?

Question

Tôi muốn hàm Python lấy một chuỗi và trả về một mảng, trong đó mỗi mục trong mảng là ký tự hoặc một mảng khác thuộc loại này. Các mảng lồng nhau được đánh dấu trong chuỗi đầu vào bằng cách bắt đầu bằng '(' và kết thúc bằng ')'.

Như vậy, chức năng sẽ hành động như thế này:

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 

Lưu ý: Tôi muốn một giải pháp đó là hoàn toàn chức năng.

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

Và,

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

Answer 2

tôi sẽ đề nghị hai cách:

Hoặc chương trình recusive parser gốc của riêng bạn như here, hoặc sử dụng pyparsing, một cái gì đó giống như

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

đây bạn mô tả một biểu thức đệ quy như một chuỗi các bản alpha, mà có thể được xen kẽ bởi các dấu ngoặc đơn cân bằng. Khi bạn kiểm tra ví dụ này cho kết quả đầu ra, bạn sẽ thấy làm thế nào để có được cấu trúc đầu ra mong muốn (mặc dù nó sẽ yêu cầu một số chỉnh sửa về phía bạn và yêu cầu một số học về pyparsing).

liên quan markus

Answer 3

Đệ quy là một cái gì đó rất mạnh mẽ mà bạn nên cố gắng sử dụng.

Đây là mã của tôi:

    # 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

Một thay nhanh chóng và khó chịu cách tiếp cận (chỉ dành riêng cho một cái gì đó khác nhau):

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

Lặp đi lặp lại.

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

Sử dụng regex và 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']]