PHP PCRE 允许字符串中的嵌套模式(递归)

Question

我得到了一个类似 1(8()3(6()7())9()3())2(4())3()1(0()3()) 的字符串 代表一棵树。 如果我们再深入一层，就会出现一个括号。同一层的数字是邻居。

现在想要添加节点，例如，我想向每个路径添加一个 5，其中第一个路径有 1，第一个路径有 3 code> 在第二层，所以我想在每个 3( 后面放置一个 5() ，它位于 1(. 因此 5() 必须添加 3 次，结果应为 1(8()3(5()6()7())9()3(5() ))2(4())3()1(0()3(5()))

问题是，我没有让代码与 PCRE 递归一起工作。如果我匹配没有固定路径的树表示字符串，如 1( 和 3( ) 它可以工作，但是当我生成具有这些固定模式的正则表达式时，它不起作用.

这是我的代码:

<?php
header('content-type: text/plain;utf-8');

$node = [1, 3, 5];
$path = '1(8()3(6()7())9()3())2(4())3()1(0()3())';

echo $path.'
';

$nes = '\((((?>[^()]+)|(?R))*)\)';
$nes = '('.$nes.')*';

echo preg_match('/'.$nes.'/x', $path) ? 'matches' : 'matches not';
echo '
';

// creates a regex with the fixed path structure, but allows nested elements in between
// in this example something like: /^anyNestedElementsHere 1( anyNestedElementsHere 3( anyNestedElementsHere ))/
$re = $nes;
for ($i = 0; $i < count($node)-1; $i++) {
    $re .= $node[$i].'\(';
    if ($i != count($node)-2)
        $re .= $nes;
}
$re = '/^('.$re.')/x';

echo str_replace($nes, '   '.$nes.'   ', $re).'
';
echo preg_match($re, $path) ? 'matches' : 'matches not';
echo '
';
// append 5()
echo preg_replace($re, '${1}'.$node[count($node)-1].'()', $path);
?>

这是输出，您可以在其中看到生成的正则表达式的样子:

1(8()3(6()7())9()3())2(4())3()1(0()3())
matches
/^(   (\((((?>[^()]+)|(?R))*)\))*   1\(   (\((((?>[^()]+)|(?R))*)\))*   3\()/x
matches not
1(8()3(6()7())9()3())2(4())3()1(0()3())

我希望你能理解我的问题，并希望你能告诉我，我的错误在哪里。

非常感谢!

Answer 1

解决方案

正则表达式

以下正则表达式以递归方式匹配嵌套括号，在第一层查找左 1(，在第二层查找左 3((作为直接子级)) .它还会尝试连续匹配，无论是在同一级别上还是向下相应级别查找另一个匹配项。

~
(?(?=\A)  # IF: First match attempt (if at start of string)   - -

  # we are on 1st level => find next "1("

  (?<balanced_brackets>
    # consumes balanced brackets recursively where there is no match
    [^()]*+
    \(  (?&balanced_brackets)*?  \)
  )*?

  # match "1(" => enter level 2
  1\(

|         # ELSE: Successive matches  - - - - - - - - - - - - - -

  \G    # Start at end of last match (level 3)

  # Go down to level 2 - match ")"
  (?&balanced_brackets)*?
  \)

  # or go back to level 1 - matching another ")"
  (?>
    (?&balanced_brackets)*?
    \)
    
    # and enter level 2 again
    (?&balanced_brackets)*?
    1\(
  )*?
)                                      # - - - - - - - - - - - -

# we are on level 2 => consume balanced brackets and match "3("
(?&balanced_brackets)*?
3\K\(  # also reset the start of the match
~x

更换

(5()

文字

Input:
1(8()3(6()7())9()3())2(4())3()1(0()3())

Output:
1(8()3(5()6()7())9()3(5()))2(4())3()1(0()3(5()))
       ^^^            ^^^                  ^^^
       [1]            [2]                  [3]

regex101 demo

---

它是如何工作的

我们首先使用conditional subpattern区分:

• 第一次比赛尝试(从第 1 级开始)以及
• 连续尝试(从第 3 级开始，以 \G assertion 为锚定)。

(?(?=\A)  # IF followed by start of string
    # This is the first attempt
|         # ELSE
    # This is another attempt
    \G    # and we'll anchor it to the end of last match
)

对于第一个匹配，我们将消耗所有不匹配 1( 的嵌套括号，以便将光标定位到第一级中的位置它可以找到成功的匹配。

• 这是一种众所周知的匹配嵌套结构的递归模式。如果您不熟悉，请引用Recursion和 Subroutines .

(?<balanced_brackets>        # ANY NUMBER OF BALANCED BRACKETS
  [^()]*+                    # match any characters 
  \(                         # opening bracket
    (?&balanced_brackets)*?  #  with nested bracket (recursively)
  \)                         # closing bracket in the main level
)*?                          # Repeated any times (lazy)

注意这是一个named group我们将在模式中多次用作子例程调用来消耗不需要的平衡括号，如 (?&balanced_brackets)*?。

下一个级别。现在，要进入第 2 级，我们需要匹配:

1\(

最后，我们将消耗所有平衡括号，直到找到第三层的开头:

(?&balanced_brackets)*?
3\(

就是这样。我们刚刚匹配了第一个匹配项，因此我们可以在该位置插入替换文本。

下一场比赛。对于连续的匹配尝试，我们可以:

• 转到与结束 ) 匹配的第 2 级 以查找另一个出现的 3(
• 进一步向下至级别 1 匹配 2 结束 )，并从那里开始使用与我们在第一场比赛中使用的相同策略进行匹配。

这是通过以下子模式实现的:

\G                             # anchored to the end of last match (level 3)
(?&balanced_brackets)*?        # consume any balanced brackets
\)                             # go down to level 2
                               #
(?>                            # And optionally
  (?&balanced_brackets)*?      #   consume level 2 brackets
  \)                           #   to go down to level 1
  (?&balanced_brackets)*?      #   consume level 1 brackets
  1\(                          #   and go up to level 2 again
)*?                            # As many times as it needs to (lazy)

总而言之，我们可以匹配第三层的开头:

(?&balanced_brackets)*?
3\(

我们还将 reset the start of match接近模式末尾时，带有 \K ，仅匹配最后一个左括号。因此，我们可以简单地替换为 (5()，避免使用反向引用。

---

PHP 代码

我们只需要调用 preg_replace() 与上面使用的值相同。

Ideone demo

---

为什么你的正则表达式失败了？

既然你问了，模式就锚定在字符串的开头。它只能匹配第一次出现的情况。

/^(   (\((((?>[^()]+)|(?R))*)\))*   1\(   (\((((?>[^()]+)|(?R))*)\))*   3\()/x

此外，它与第一次出现不匹配，因为构造 (?R) 递归了 整个 模式(尝试匹配 ^ 再次)。我们可以将 (?R) 更改为 (?2)。

但主要原因是因为它在任何打开 \( 之前不消耗字符。例如:

Input:
1(8()3(6()7())9()3())2(4())3()1(0()3())
  ^
  #this "8" can't be consumed with the pattern

还有一个行为应该考虑:PCRE treats recursion as atomic 。因此，您必须确保该模式将消耗不需要的括号，如上例所示，但也要避免在各自的级别中匹配 1( 或 3(。