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

Question

显然这个问题经常出现, 阅读

Regular expression to detect semi-colon terminated C++ for & while loops

思考了一下，我编写了一个函数来返回嵌套的小括号内的内容。

这个函数可以轻松地扩展到任何正则表达式对象，我在此张贴并等待您的想法和考虑。

如果能提供任何重构建议将不胜感激。

(请注意，我仍然是 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]]

- justin cress

Answer 1

您没有明确说明函数的规范，但这种行为对我来说似乎是错误的：

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

关于你的代码的其他评论：

• 文档字符串说“generate”，但函数返回一个列表，而不是生成器。
• 既然只有一个字符串被返回，为什么要将其返回为列表？
• 在什么情况下函数可以返回字符串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')]

- Gareth Rees

---

与ParseNestedParen('(a)(b)(c)', 0)相关的行为实际上是正确的，但我的函数不适合这个任务，我编写该函数时考虑的是string = "some_function(another_function(some_argument))"。为什么要返回列表？不应该。非常好的观点，谢谢！ 我什么时候会返回失败？我不知道。也许永远不会。这是我编写函数时留下的。重复调用find all是浪费的吗？那我应该只创建一个列表countparen = [re.findall(str) for str in ["(",")"]]并使用它吗？还有其他方法可以重新平衡括号吗？感谢您的评论！ - justin cress

很难说对于不平衡的括号应该采取什么正确的处理方式，因为我不知道该函数将被用于什么目的。最有可能的是，不平衡的字符串是一种输入错误，应该被忽略（例如语法高亮的应用）或作为错误抛出（例如编译的应用）。 - Gareth Rees

list(parenthetic_contents('a(b(c)(d)e)(f)g')) actually gives me [(1, 'c'), (1, 'd'), (0, 'b(c)(d)e'), (0, 'f')] - Peter

@Peter：那跟帖子中的示例代码不一样。 - Gareth Rees

惊叹于这个解决方案的美丽。绝对的代码。 - Martin

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

- Olivier Melançon

---

这太棒了，你有更多关于Python中不同自动机行为的参考资料吗？或者如何用简单的方式编写它们的Python代码？ - DaniPaniz

@DaniPaniz 这是一个经典的例子，它状态很少，所以在Python中很容易编写。更复杂的例子通常需要解析器生成器，你不会手写它们。 - Olivier Melançon

Answer 3

下面是我的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']

- Nitesh Mistry

Answer 4

#!/usr/bin/env python
import re

def ParseNestedParen(string, level):
    """
    Generate strings contained in nested (), indexing i = level
    """
    if len(re.findall("\(", string)) == len(re.findall("\)", string)):
        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 len(re.findall("\(", string)) > len(re.findall("\)", string)):
        return ParseNestedParen(string + ')', level)

    elif len(re.findall("\(", string)) < len(re.findall("\)", string)):
        return ParseNestedParen('(' + string, level)

    else:
        return 'fail'

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

测试：

if __name__ == '__main__':

    teststring = "outer(first(second(third)second)first)outer"

    print(ParseNestedParen(teststring, 0))
    print(ParseNestedParen(teststring, 1))
    print(ParseNestedParen(teststring, 2))

    teststring_2 = "outer(first(second(third)second)"

    print(ParseNestedParen(teststring_2, 0))
    print(ParseNestedParen(teststring_2, 1))
    print(ParseNestedParen(teststring_2, 2))

    teststring_3 = "second(third)second)first)outer"

    print(ParseNestedParen(teststring_3, 0))
    print(ParseNestedParen(teststring_3, 1))
    print(ParseNestedParen(teststring_3, 2))

输出：

Running tool: python3.1

['first(second(third)second)first']
['second(third)second']
['third']
['first(second(third)second)']
['second(third)second']
['third']
['(second(third)second)first']
['second(third)second']
['third']
>>> 

- justin cress

---

所以，正如你所看到的，该函数允许不平衡的括号，但并不是非常优雅的方式。 - justin cress