使用PCRE匹配n>0的a^n b^n c^n序列

Question

使用PCRE匹配n>0的a^n b^n c^n序列

14

如何使用PCRE匹配a^n b^n c^n (n > 0)？

以下情况应该匹配：

abc
aabbcc
aaabbbccc

以下情况不应匹配：

abbc
aabbc
aabbbccc

这是我尝试过的正则表达式：/^(a(?1)?b)$/gmx，但它会匹配到n > 0 的a^n b^n：

ab
aabb
aaabbb

在线演示

注意：这个问题与这个问题相同，只是语言不同。

- HamZa

使用平衡组 http://www.regular-expressions.info/balancing.html - Max Carroll

1

PCRE不支持平衡组。 - HamZa

2

在这种情况下，这是一个好问题...我会投赞成票。 - Max Carroll

我认为这个问题也可以用Qtax技巧来解决。另请参阅捕获量词和量词算术。向那些能够使用它或想出其他技巧的人致敬！ - HamZa

3

重要提示：polygenelubricants的一系列正则表达式文章第二章：如何使用Java正则表达式匹配a^n b^n？ - Unihedron

2个回答

11

首先，让我们解释一下你拥有的模式：

^               # Assert begin of line
    (           # Capturing group 1
        a       # Match a
        (?1)?   # Recurse group 1 optionally
        b       # Match b
    )           # End of group 1
$               # Assert end of line

使用以下修改器：

g: global, match all
m: multiline, match start and end of line with ^ and $ respectively
x: extended, indentation are ignored with the ability to add comments with #

递归部分是可选的，以便最终退出“无限”递归。

我们可以使用上面的模式来解决问题。我们需要添加一些正则表达式来匹配c部分。问题是当aabb在aabbcc中匹配时，它已经被消耗了，这意味着我们无法回溯。

解决方案？使用前瞻！前瞻是零宽度的，这意味着它不会消耗字符并向前移动。看看下面的例子：

^                    # Assert begin of line
    (?=              # First zero-with lookahead
        (            # Capturing group 1
            a        # Match a
            (?1)?    # Recurse group 1 optionally
            b        # Match b
        )            # End of group 1
        c+           # Match c one or more times
    )                # End of the first lookahead

    (?=              # Second zero-with lookahead
        a+           # Match a one or more times
        (            # Capturing group 2
            b        # Match b
            (?2)?    # Recurse group 2 optionally
            c        # Match c
        )            # End of group 2
    )                # End of the second lookahead
a+b+c+               # Match each of a,b and c one or more times
$                    # Assert end of line

在线演示

基本上，我们首先断言存在 a^n b^n，并且随后断言 b^n c^n，这将导致 a^n b^n c^n。

- HamZa

2

你能不能简化一下，去掉 a+b+c+ 并且不使用向前查看来处理第二部分？ - Bergi

1

@Bergi 正确。我只是想让它变得清晰和简单。 - HamZa

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Unihedron · Accepted Answer

Qtax技巧

（强大的自引用捕获组）

^(?:a(?=a*(\1?+b)b*(\2?+c)))+\1\2$

这种解决方案也被称为“Qtax技巧”，因为它使用的技术与Qtax的"vertical" regex matching in an ASCII "image"相同。

所涉及的问题归结为需要断言三个组匹配的长度相同。简化版如下：

xyz

其中，x、y和z实际上只是具有匹配长度为n的变量与a、b和c的子模式。使用带有自引用捕获组的表达式，我们可以添加我们指定的字符到每个前瞻重复中，这可以有效地用于“计数”：

aaabbbccc
 ^  ^  ^

这可以通过以下方式实现：

(?:a…)+ 匹配子模式a的一个字符。使用(?=a*，我们直接跳到“计数器”。
(\1?+b) 捕获组（\1）有效地消耗了之前匹配的任何内容，如果存在的话，并使用贪婪匹配，不允许回溯，如果计数器失步，则匹配失败 - 即，子模式b的数量比子模式a的数量多。在第一次迭代中，它不存在，因此不会匹配任何内容。然后匹配子模式b的一个字符。它被添加到捕获组中，有效地“计数”组中的一个b。使用b*，我们直接跳到下一个“计数器”。
(\2?+c) 捕获组（\2）有效地消耗了之前匹配的任何内容，就像上述捕获组一样。因为这个额外的字符捕获与先前的组一样工作，所以可以允许字符在这些字符组中保持长度同步。假设连续的a..b..c..序列：

_{（抱歉我的绘画技巧。）}

第一次迭代：

| The first 'a' is matched by the 'a' in '^(?:a…)'.
| The pointer is stuck after it as we begin the lookahead.
v,- Matcher pointer
aaaa...bbbbbbbb...cccc...
 ^^^   |^^^       ^
skipped| skipped  Matched by c in (\2?+c);
by a*  | by b*         \2 was "nothing",
       |               now it is "c".
       Matched by b
       in (\1?+b).
     \1 was "nothing", now it is "b".

第二次迭代：

 | The second 'a' is matched by the 'a' in '^(?:a…)'.
 | The pointer is stuck after it as we begin the lookahead.
 v,- Matcher pointer
aaaa...bbbbbbbb...cccc...
       /|^^^      |^
eaten by| skipped |Matched by c in (\2?+c);
\1?+    | by b*   |     '\2' was "nothing",
  ^^    |      \2?+     now it is "cc".
 skipped|
 by a*  \ Matched by b
          in (\1?+b).
          '\1' was "nothing", now it is "bb".

如上所述，由于三个组分别"消耗"了一个a、b和c，它们以轮流方式匹配，并且由(?:a…)+、(\1?+b)和(\2?+c)组分别计数。通过我们开始的额外锚定和捕获，我们可以断言我们匹配了xyz（代表上面的每个组），其中x、y和z分别是aⁿ、bⁿ和cⁿ。

作为奖励，您可以使用以下方法"计数":

模式：^(?:a(?=a*(\1?+b)b*(\2?+c)))+\1{3}\2$
匹配：abbbc
aabbbbbbcc
aaabbbbbbbbbccc

模式：^(?:a(?=a*(\1?+bbb)b*(\2?+c)))+\1\2$
匹配：abbbc
aabbbbbbcc
aaabbbbbbbbbccc