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

Question

正如标题所述，这里是一个示例输入：

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

当然，匹配的字符串将会被递归处理。

我希望第一次递归能够匹配到：

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

后续的流程无需多言…

- gordomium

---

那样反复解析括号会非常低效。使用真正的解析器。（带有逐个字符循环的计数器就足够了）。 - nneonneo

看起来你需要类似Lisp的东西。 - Ingo

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");
}

将打印以下内容：

----------
(外层
   (居中
     (内部)
     (内部)
   居中)
 外层)
----------
(外层
   (内部)
 外层)
----------
(外层
 外层)

或者，使用PHP等效代码：

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

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

print_r($matches);

生成以下内容：

阵列
(
    [0] => 阵列
        (
            [0] => (外部
     (中心
       (内部)
       (内部)
     中心)
 外部)
            [1] => (外部
     (内部)
 外部)
            [2] => (外部
 外部)
        )
...

解释如下：

（          #开始第一组
  \(       #匹配一个括号'(' 
  （        #开始第二组
     [^()]  #匹配不是‘（’和‘）’的任何字符
     |      #或者
    (?R)   #递归的匹配整个模式
  ）*       #结束第二组，重复零次或多次
  \)       #匹配一个右括号')' 
）          #结束第一组

编辑

请注意@Goozak的评论：

 

更好的模式可能是\(((?>[^()]+)|(?R))*\)（来自PHP:Recursive patterns）。对于我的数据，Bart的模式在遇到没有嵌套的（长字符串）时会使PHP崩溃。这个模式可以完全处理我的数据。

- Bart Kiers

---

@Goozak，注意我通常尽可能简单地发布正则表达式模式，以便更容易理解。但你是对的，通过原子组和贪婪匹配[^()]可以进行优化。我会在我的答案中加入你的评论。 - Bart Kiers

@BartKiers，我使用“更好的模式”这个词可能有点过分了。 :-) 我尝试了你的模式，发现它在我的数据上崩溃了。当我发现PHP帮助模式可行时，我只是想提到这一点，以防其他人遇到相同的情况。这绝对不是对你原来的模式的贬低评论。 - Goozak

没问题！你提出了一个有价值的观点：在大量输入的情况下，我的原始模式表现不佳 :) - Bart Kiers

实际上，如果在两个括号之间有一个转义的括号，这种方法就不起作用了。你有什么想法如何解决这个问题吗？((foo)bar\)baz\\)（我正在尝试使用RegEx解析一个RegEx字符串...这就是为什么我必须考虑转义字符的原因：-()） - boesing

@boesing 请使用 (?:[^\\()]|\\[\\()]) 替代 [^()]。 - Bart Kiers

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

- nneonneo

---

一个使用示例会很方便。 - Wiktor Stribiżew

Answer 3

我发现了一个简单的正则表达式，利用递归提取所有嵌套的平衡组，但是得到的解决方案并不像你预期的那样直接。

正则表达式模式为：(1(?:\1??[^1]*?2))+ 示例输入：1ab1cd1ef2221ab1cd1ef222 为了简化，我将1表示为打开括号，2表示为关闭括号。字母字符代表一些内部数据。我将重新编写输入，以便更容易解释。

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

            |_1|
       |______2__|
|_____________3_____|

在第一次迭代中，正则表达式将匹配第一个同级组1ab1cd1ef222中最内部的子组1ef2。如果我们记住它及其位置，并删除此组，剩下的将是1ab1cd22。如果我们继续使用正则表达式，它将返回1cd2，最后是1ab2。然后，它将以相同的方式继续解析第二个同级组。

从这个例子中可以看出，正则表达式将按照括号定义的层次结构正确提取子字符串。在第二次迭代期间，特定子字符串在层次结构中的位置将被确定，如果它在字符串中的位置在第二次迭代的子字符串之间，则它是一个子节点，否则它是一个同级节点。

从我们的例子中可以看出：

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，它是来自另一个同级节点的分支等等...

在我们移动到父级之前，我们必须迭代并删除所有同级节点。因此，我们必须按迭代顺序记住所有这些同级节点。

- Elvedin Hamzagic

---

我已经整晚在寻找这个解决方案了。这是我找到的唯一有用的一个。我最终使用的“翻译”的正则表达式是 (\[(?:\[??[^\[]*?\]))。 - patrick

@Quonux，那很可能是这样，我在一个PHP程序中使用上述正则表达式，效果非常好。 - patrick

如果有一种处理/比较索引的方法，那么使用正则表达式来获取它们就没有意义了。 - irvnriir

Answer 4

基于nneonneo的帖子的Delphi Pascal代码：

您需要一个名为btnRun的按钮的表单。在源代码中，将“arnolduss”替换为您在DownLoads文件夹中的名称。请注意ParseList创建的输出中的堆栈级别。显然，同一类型的括号必须在同一堆栈级别上打开和关闭。现在，您将能够提取所谓的每个堆栈级别的组。

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

Type TCharPos = record
  Level: integer;
  Pos: integer;
  Char: string;
end;

type
  TForm1 = class(TForm)
    btnRun: TButton;
    procedure btnRunClick(Sender: TObject);
  private
    { Private declarations }
    procedure FormulaFunctionParser(var CharPos: array of TCharPos;
       const formula, LBracket, RBracket: string; var itr, iChar,
       iLevel: integer; var ParseList: TStringList);
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.btnRunClick(Sender: TObject);
var
  formula: string;
  CharPos: array of TCharPos;
  itr, iChar, iLevel: integer;
  ParseList: TStringList;
begin
  screen.Cursor := crHourGlass;
  itr := 0;
  iChar := 1;
  iLevel := 0;
  ParseList := TStringList.Create;
  try
    formula := Trim('add(mul(a,add(b,c)),d) + e - sub(f,g)');
    ParseList.Add(formula);
    ParseList.Add('1234567890123456789012345678901234567890');

    SetLength(CharPos, Length(formula));
    FormulaFunctionParser(CharPos[0], formula, '(', ')', itr, iChar, iLevel, ParseList);
  finally
    ParseList.SaveToFile('C:\Users\arnolduss\Downloads\ParseList.txt');
    FreeAndNil(ParseList);
    screen.Cursor := crDefault;
  end;
end;

//Based on code from nneonneo in: https://dev59.com/MmUp5IYBdhLWcg3w6q2q
procedure TForm1.FormulaFunctionParser(var CharPos: array of TCharPos;
       const formula, LBracket, RBracket: string; var itr, iChar,
       iLevel: integer; var ParseList: TStringList);
  procedure UpdateCharPos;
  begin
    CharPos[itr-1].Level := iLevel;
    CharPos[itr-1].Pos := itr;
    CharPos[itr-1].Char := formula[iChar];

    ParseList.Add(IntToStr(iLevel) + '  ' + intToStr(iChar) + ' = ' + formula[iChar]);
  end;
begin
  while iChar <= length(formula) do
  begin
    inc(itr);
    if formula[iChar] = LBracket then
    begin
      inc(iLevel);
      UpdateCharPos;
      inc(iChar);
      FormulaFunctionParser(CharPos, formula, LBracket, RBracket, itr, iChar, iLevel, ParseList);
    end
    else
    if formula[iChar] = RBracket then
    begin
      UpdateCharPos;
      dec(iLevel);
      inc(iChar);
    end
    else
    begin
      UpdateCharPos;
      inc(iChar);
    end;
  end;
end;

end.

- Nols Smit