如何在平衡括号之间得到一个表达式

Question

假设给出了以下类型的字符串:

"(this is (haha) a string(()and it's sneaky)) ipsom (lorem) bla"

我想提取括号中最顶层的子串.即我想获得字符串:"this is (haha) a string(()and it's sneaky)"和"lorem".

有一个很好的pythonic方法来做到这一点？正则表达式显然不适用于此任务,但也许有一种方法可以让xml解析器完成这项工作？对于我的应用程序,我可以假设括号形成良好,即不像(()(().

Answer 1

这是堆栈的标准用例:您按字符方式读取字符串,每当遇到左括号时,将符号推送到堆栈; 如果遇到右括号,则从堆栈中弹出符号.

由于您只有一种类型的括号,因此实际上并不需要堆栈; 相反,只要记住有多少个开括号就足够了.

另外,为了提取文本,我们还记得当第一级上的括号打开时部件开始的位置,并在遇到匹配的右括号时收集结果字符串.

这看起来像这样:

string = "(this is (haha) a string(()and it's sneaky)) ipsom (lorem) bla"

stack = 0
startIndex = None
results = []

for i, c in enumerate(string):
    if c == '(':
        if stack == 0:
            startIndex = i + 1 # string to extract starts one index later

        # push to stack
        stack += 1
    elif c == ')':
        # pop stack
        stack -= 1

        if stack == 0:
            results.append(string[startIndex:i])

print(results)
# ["this is (haha) a string(()and it's sneaky)", 'lorem']