如何解析字符串并返回嵌套数组？

Question

我需要一个Python函数，它接收一个字符串并返回一个数组。数组中的每个项都是一个字符或者另一个这种类型的数组。输入字符串中以'('开头且以')'结尾的嵌套数组将被标记为嵌套数组。

因此，该函数的行为如下：

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

注意：我更喜欢一个纯函数式的解决方案。

- Tespa42

---

在这里使用递归是最合适的。在令牌流中找到一个'('意味着递归进入。在顶层调用中找到一个')'意味着存在平衡不匹配。 - user2246674

递归确实很好用，只要字符串不太长。请记住，这可能需要一个包装函数，因为我们需要检查'('的数量是否与')'的数量匹配。如果匹配，则调用递归函数。如果不匹配，则给出适当的错误消息。 - Truerror

是的，我知道我将在这里使用递归。我知道如何编写一个使用堆栈的函数，返回字符串中括号是否平衡和有序，但尝试返回嵌套数组却让我困惑。这不是作业。这是更大的解析程序的一部分。 - Tespa42

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

同时，

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

- Jared

---

你想尝试用函数式风格来重写这个吗？ - Tespa42

@FinalZero 你是什么意思？这已经是一个递归解决方案了。 - Jared

我的意思是以不使用 iter 和 next 的方式。 - Tespa42

答案不是纯函数式的，但我仍然接受它，因为它帮助我理解并编写了纯函数式的解决方案，这需要 foo 返回一个元组而不仅仅是一个数组。 - Tespa42

Answer 2

迭代。

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'

- falsetru

---

+1 而且你不需要 result：只需设置 stack = [[]] 然后返回 stack.pop()。这样更加纯粹 -- 只有栈。 - FMc

Answer 3

我建议有两种方法：

一种是像这里所示的那样编写自己的递归下降解析器，或者使用像pyparsing这样的工具。

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

在这里，你将递归表达式描述为由字母序列组成的一组，其中可以插入平衡括号。当你检查此示例的输出时，你将看到如何获得所需的输出结构（尽管这将需要你进行一些调整并学习有关pyparsing的知识）。

祝好， 马库斯

- fricke

Answer 4

使用 正则表达式 和 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']]

- Ashwini Chaudhary

Answer 5

一种相对快速而不太优雅的方法（只是为了尝试不同的方式）：

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

- Alex L

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

- Janne Karila

Answer 7

递归是一种非常强大的工具，你应该尝试使用它。

这是我的代码：

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

- Harry Wang

---

我的代码没问题，但在答案区域显示时出错了...我正在尝试修复它。我用'<'替换了'<'，然后就好了！ - Harry Wang