在Python中解析嵌套括号，按层级提取内容

Question

显然，这个问题经常出现。在阅读了

用于检测以分号结束的C++ for和while循环的正则表达式

并思考了一段时间后，我写了一个函数，可以返回任意数量嵌套的括号()内的内容。

这个函数可以很容易地扩展到任何正则表达式对象，发在这里希望听听大家的想法和建议。

如果有任何重构的建议，我会很感激。

（注意，我还是Python新手，不想花时间去弄清楚如何抛出异常之类的，所以如果函数无法理解发生了什么，就直接返回'fail'。）

编辑后的函数考虑到了注释：

def ParseNestedParen(string, level):
    """
    Return string contained in nested (), indexing i = level
    """
    CountLeft = len(re.findall("\(", string))
    CountRight = len(re.findall("\)", string))
    if CountLeft == CountRight:
        LeftRightIndex = [x for x in zip(
        [Left.start()+1 for Left in re.finditer('\(', string)], 
        reversed([Right.start() for Right in re.finditer('\)', string)]))]

    elif CountLeft > CountRight:
        return ParseNestedParen(string + ')', level)

    elif CountLeft < CountRight:
        return ParseNestedParen('(' + string, level)

    return string[LeftRightIndex[level][0]:LeftRightIndex[level][1]]

Answer 1

下面是我用Python写的解决方案，时间复杂度是O(N)，也就是说处理的时间和数据的数量成正比。

str1 = "(a(b(c)d)(e(f)g)hi)"

def content_by_level(str1, l):
    level_dict = {}
    level = 0
    level_char = ''
    for s in str1:
        if s == '(':
            if level not in level_dict:
                level_dict[level] = [level_char]
            elif level_char != '':
                level_dict[level].append(level_char)
            level_char = ''
            level += 1
        elif s == ')':
            if level not in level_dict:
                level_dict[level] = [level_char]
            elif level_char != '':
                level_dict[level].append(level_char)
            level_char = ''
            level -= 1
        else:
            level_char += s
    
    print(level_dict) # {0: [''], 1: ['a', 'hi'], 2: ['b', 'd', 'e', 'g'], 3: ['c', 'f']}
    return level_dict[l]

print(content_by_level(str1,0)) # ['']
print(content_by_level(str1,1)) # ['a', 'hi']
print(content_by_level(str1,2)) # ['b', 'd', 'e', 'g']
print(content_by_level(str1,3)) # ['c', 'f']

Answer 2

括号匹配需要一个解析器，这个解析器可以理解括号的开和关。虽然市面上有一些现成的库可以用，但其实规则很简单，我们完全可以自己从头写一个：

def push(obj, l, depth):
    while depth:
        l = l[-1]
        depth -= 1

    l.append(obj)

def parse_parentheses(s):
    groups = []
    depth = 0

    try:
        for char in s:
            if char == '(':
                push([], groups, depth)
                depth += 1
            elif char == ')':
                depth -= 1
            else:
                push(char, groups, depth)
    except IndexError:
        raise ValueError('Parentheses mismatch')

    if depth > 0:
        raise ValueError('Parentheses mismatch')
    else:
        return groups

print(parse_parentheses('a(b(cd)f)')) # ['a', ['b', ['c', 'd'], 'f']]

Answer 3

你没有清楚说明你的函数具体是干什么的，但我觉得这个行为看起来不太对：

>>> ParseNestedParen('(a)(b)(c)', 0)
['a)(b)(c']
>>> nested_paren.ParseNestedParen('(a)(b)(c)', 1)
['b']
>>> nested_paren.ParseNestedParen('(a)(b)(c)', 2)
['']

关于你代码的其他评论：

• 文档说明里说是“生成”，但这个函数返回的是一个列表，而不是生成器。
• 既然只会返回一个字符串，为什么要把它放在一个列表里返回呢？
• 在什么情况下这个函数会返回字符串 fail 呢？
• 反复调用 re.findall 然后丢掉结果是浪费资源。
• 你试图重新平衡字符串中的括号，但你每次只处理一个括号：

>>> ParseNestedParen(')' * 1000, 1)
RuntimeError: maximum recursion depth exceeded while calling a Python object

正如Thomi在你链接的问题中所说的，“正则表达式真的不是解决这个问题的好工具！”

---

解析嵌套表达式的常用方法是使用栈，像这样：

def parenthetic_contents(string):
    """Generate parenthesized contents in string as pairs (level, contents)."""
    stack = []
    for i, c in enumerate(string):
        if c == '(':
            stack.append(i)
        elif c == ')' and stack:
            start = stack.pop()
            yield (len(stack), string[start + 1: i])

>>> list(parenthetic_contents('(a(b(c)(d)e)(f)g)'))
[(2, 'c'), (2, 'd'), (1, 'b(c)(d)e'), (1, 'f'), (0, 'a(b(c)(d)e)(f)g')]