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

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

许多正则表达式实现不允许您匹配任意数量的嵌套.但是,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的评论:

一个更好的模式可能是\(((?>[^()]+)|(?R))*\)(来自PHP:递归模式).对于我的数据,Bart的模式在遇到没有嵌套的(长字符串)时崩溃了PHP.这个模式经历了我的所有数据没有问题.

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

Answer 3

我发现这个简单的正则表达式使用递归提取所有嵌套的平衡组,尽管得到的解决方案并不像你期望的那样简单:

正则表达式模式: (1(?:\1??[^1]*?2))+

样本输入: 1ab1cd1ef2221ab1cd1ef222

为简单起见,我提出1了开放式和2封闭式支架.Alpha字符代表一些内部数据.我会重写输入,以便于解释.

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

            |_1|
       |______2__|
|_____________3_____|

在第一次迭代中,正则表达式将匹配1ef2第一个兄弟组中最内部的子组1ab1cd1ef222.如果我们记住它并且它的位置,并删除这个组,那么将会存在1ab1cd22.如果我们继续使用正则表达式,它将返回1cd2,最后1ab2.然后,它将继续以相同的方式解析第二个兄弟组.

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

从我们的例子:

1. 1ab1cd1ef222 1ab1cd1ef222,迭代匹配1ef2,带索引6,

2. 1ab1cd22 1ab1cd1ef222,迭代匹配1cd2,带索引3,以6.结尾.因为3<< 6= 6,第一个子串是第二个子串的子节点.

3. 1ab2 1ab1cd1ef222,迭代匹配1ab2,带索引0,以3.结尾.因为0<< 3= 3,第一个子串是第二个子串的子节点.

4. 1ab1cd1ef222,迭代匹配1ef2,与指数6,因为它不是3< 0<= 6,它是从另一个兄弟,等支...

我们必须迭代并删除所有兄弟姐妹才能转移到父母.因此,我们必须按照它们在迭代中出现的顺序记住所有兄弟姐妹.