如何使用正则表达式匹配嵌套括号？

Question

正如标题所说，以下是一个输入示例：

 (outer
   (center
     (inner)
     (inner)
   center)
 ouer)
 (outer
   (inner)
 ouer)
 (outer
 ouer)

当然，匹配的字符串将通过递归进行处理。

我希望第一个递归匹配：

 [
 (outer
   (center
     (inner)
     (inner)
   center)
 ouer),
 (outer
   (inner)
 ouer),
 (outer
 ouer)]

之后的过程不用说。。。

Answer 1

匿名用户

我发现了一个简单的正则表达式，它使用递归提取所有嵌套的平衡组，尽管最终的解决方案并不像您预期的那样简单：

正则表达式模式：（1（？：\1？？[^1]*？2）

示例输入：1AB1CD1EF22221AB1CD1EF222

为了简单起见，我把1放在开放括号中，把2放在封闭括号中。字母字符代表一些内部数据。我将重写输入，以便易于解释。

1  ab  1 cd 1ef2 2  2     1  ab  1 cd 1ef2 2  2

            |_1|
       |______2__|
|_____________3_____|

在第一次迭代中，正则表达式将匹配第一个兄弟姐妹组中最内部的子组1ef21ab1cd1ef222。如果我们记住它和它的位置，并删除这个组，将保留1ab1cd22。如果我们继续使用正则表达式，它将返回1cd2，最后返回1ab2。然后，它将继续以相同的方式解析第二个兄弟姐妹组。

正如我们从这个例子中看到的，正则表达式将正确地提取出出现在括号定义的层次结构中的子串。在第二次迭代中，特定子串在层次结构中的位置将被确定，如果它在字符串中的位置在第二次迭代的子串之间，那么它是一个子节点，否则它是一个兄弟节点。

从我们的例子来看：

>

1ab1cd1ef222 1ab1cd1ef222，迭代匹配1ef2，索引6，

1ab1cd22 1ab1cd1ef222，迭代匹配1cd2，索引3，以6结尾。因为3

1ab2 1ab1cd1ef222，迭代匹配1ab2，索引0，以3结尾。因为0

1ab1cd1ef222，迭代匹配1ef2，索引6，因为它不是3

在移到父级之前，我们必须迭代并删除所有兄弟姐妹。因此，我们必须按照迭代中出现的顺序记住所有兄弟姐妹。

Answer 2

不要使用正则表达式。

相反，一个简单的递归函数就足够了。以下是总体结构：

def recursive_bracket_parser(s, i):
    while i < len(s):
        if s[i] == '(':
            i = recursive_bracket_parser(s, i+1)
        elif s[i] == ')':
            return i+1
        else:
            # process whatever is at s[i]
            i += 1
    return i

例如，下面是一个将输入解析为嵌套列表结构的函数：

def parse_to_list(s, i=0):
    result = []
    while i < len(s):
        if s[i] == '(':
            i, r = parse_to_list(s, i+1)
            result.append(r)
        elif s[i] == ')':
            return i+1, result
        else:
            result.append(s[i])
            i += 1
    return i, result

像这样调用parse_to_list（'（（a）（（b））（（c）（d））（efg'）会产生[[['a']，''，[['b']]，''，[[c']，['d']]，'e'，'f'，'g']的结果。

Answer 3

许多正则表达式实现不允许匹配任意数量的嵌套。然而，Perl、PHP和。NET支持递归模式。

Perl中的演示：

#!/usr/bin/perl -w

my $text = '(outer
   (center
     (inner)
     (inner)
   center)
 ouer)
 (outer
   (inner)
 ouer)
 (outer
 ouer)';

while($text =~ /(\(([^()]|(?R))*\))/g) {
  print("----------\n$1\n");
}

将打印：

----------
(outer
   (center
     (inner)
     (inner)
   center)
 ouer)
----------
(outer
   (inner)
 ouer)
----------
(outer
 ouer)

或者，PHP等价物：

$text = '(outer
   (center
     (inner)
     (inner)
   center)
 ouer)
 (outer
   (inner)
 ouer)
 (outer
 ouer)';

preg_match_all('/(\(([^()]|(?R))*\))/', $text, $matches);

print_r($matches);

它产生：

Array
(
    [0] => Array
        (
            [0] => (outer
   (center
     (inner)
     (inner)
   center)
 ouer)
            [1] => (outer
   (inner)
 ouer)
            [2] => (outer
 ouer)
        )

...

一个解释：

(          # start group 1
  \(       #   match a literal '('
  (        #   group 2
    [^()]  #     any char other than '(' and ')'
    |      #     OR
    (?R)   #     recursively match the entir pattern
  )*       #   end group 2 and repeat zero or more times
  \)       #   match a literal ')'
)          # end group 1

注意@Goozak的评论：

更好的模式可能是\（？