使用正则表达式（PCRE）匹配a^n b^n c^n（例如“aaabbbccc”）。

Question

使用正则表达式（PCRE）匹配a^n b^n c^n（例如“aaabbbccc”）。

46

众所周知，现代正则表达式实现（尤其是PCRE）与正则文法的最初概念几乎没有任何相似之处。例如，您可以使用这个正则表达式（演示）来解析典型的上下文无关文法 {aⁿbⁿ; n>0}（例如aaabbb）。

~^(a(?1)?b)$~

我的问题是：你能做到什么程度？是否也可以使用PCRE解析上下文敏感语法{aⁿbⁿcⁿ;n>0}（例如aaabbbccc）？

- NikiC

3

(?R)和~是正则表达式中的特殊符号，(?R)表示递归匹配，~表示取反。preg_match('a*b*c*',...)存在问题是因为它会匹配到一些不符合预期的字符串，例如ac或bc。 - Chriszuma

7

首先，PHP正则表达式需要定界符。这就是~的作用。其次，abc*匹配acccccccccc。 - NullUserException

6

@Chriszuma：~ 只是分隔符（你也可以使用 / 和许多其他字符）。 (?R) 表示递归。它的意思是“再次将整个正则表达式放在这里”。 - NikiC

1

@Chriszuma：Python 的 re 模块不支持递归正则表达式，虽然曾经有过这个需求，但是后来被放弃了（http://bugs.python.org/msg83993）。在 Python 中唯一的替代方案是 pyparsing。 - Orbling

4

等等，我现在明白了。棘手的部分是对于每个组来说，n 必须是相同的，对吗？所以如果有5个a，那么就必须恰好有5个b和5个c。不，我知道这是没有递归不可能做到的，即使你可以用递归做到，我肯定也不知道怎么做。 - Justin Morgan

显示剩余16条评论

4个回答

12

以下是使用.NET正则表达式和平衡组的另一种解决方案：

^(?'a'a)+(?'b-a'b)+(?(a)(?!))(?'c-b'c)+(?(b)(?!))$

虽然不是PCRE，但可能会有兴趣。

示例： http://ideone.com/szhuE

编辑：为a组添加了缺失的平衡检查，并添加了在线示例。

- Qtax

2

@NikiC：实际上它们非常简单。在.NET中，每次使用命名捕获语法(?'a' ... )时，它实际上是将捕获推送到捕获堆栈中。然后，语法(?'-a' ... )从a堆栈中弹出一个项目（如果堆栈为空，则失败）。您还可以在条件正则表达式中使用捕获堆栈，这就是语法(?(a) ... )的作用。如果堆栈包含项目，则堆栈计算为true。 - porges

2

因此，上面的代码是这样做的：将所有“a”捕获推入堆栈，将所有“b”捕获推入堆栈（每个“b”弹出一个“a”），然后断言“a”堆栈为空（（？！）是无条件失败），接着使用“b”堆栈重复相同的操作来处理“c”。 - porges

1

@Porges，只是提醒一下，它不必是一个命名捕获组。未命名的同样有效（除了 (?'-x'...) 不会创建新的/添加到堆栈）。我的正则表达式的较短版本如下：^(a)+(?'b-1'b)+(?(1)(?!))(?'-b'c)+(?(b)(?!))$。 - Qtax

12

我的问题是：你可以走多远？

为了避免创建一堆标点符号的代码，使其难以阅读，我冒着被踩的风险回答一个不同但非常相关的问题：你应该走多远？

正则表达式解析器是工具箱中必备的妙物，但它们并不是编程的全部。能够以易于阅读的方式编写解析器也是一件很好的事情。

在使用正则表达式时，应该在其开始让你的代码难以理解之前停止。超出这个范围，它们的价值最多是可疑的，在最坏的情况下会对代码造成破坏。对于这种特定情况，与其使用类似下面这样丑陋的东西：

~^(?=(a(?-1)?b)c)a+(b(?-1)?c)$~x

(向NikiC道歉)，由于维护这个正则表达式的绝大多数人要么必须完全替换它，要么需要花费相当可观的时间来阅读和理解。因此，你可能想考虑使用非正则表达式的“真正解析器”解决方案（伪代码）：

# Match "aa...abb...bcc...c" where:
# - same character count for each letter; and
# - character count is one or more.

def matchABC (string str):
    # Init string index and character counts.
    index = 0
    dim count['a'..'c'] = 0

    # Process each character in turn.
    for ch in 'a'..'c':
        # Count each character in the subsequence.
        while index < len(str) and str[index] == ch:
            count[ch]++
            index++

    # Failure conditions.
    if index != len(str):        return false # did not finish string.
    if count['a'] < 1:           return false # too few a characters.
    if count['a'] != count['b']: return false # inequality a and b count.
    if count['a'] != count['c']: return false # inequality a and c count.

    # Otherwise, it was okay.
    return true

将来维护这段代码会容易得多。我通常建议人们假设后来的那些人（他们需要维护你编写的代码）是精神病患者，他们知道你住在哪里 - 在我的情况下，这可能是对的一半，我不知道你住在哪里 :-)。

除非您真正需要这种类型的正则表达式（有时候确实存在很好的理由，例如在解释性语言中提高性能），否则应优化可读性为首要目标。

- paxdiablo

4

这些模式并不适用于生产代码，它们纯粹是用于娱乐。
你的代码允许其他字符 - abc! 会返回 true。
你不在意顺序 - caabbc 也会返回 true。
像大多数代码一样：代码行数越多，错误就越多。
你可以在单次遍历中计算字符：while index < len(str): count[str[index]]++, index++。
你可以测试和注释模式。看起来很棒。

- Kobi

1

@Kobi，你需要重新检查我的代码和问题规格。它不允许超过结尾的更多字符，这由第一个失败检查处理。它不允许无序的abc序列 - for循环会处理这个问题。实际上，你的第5点是错误的，因为它将允许abcabc通过，这显然是不正确的。 - paxdiablo

2

@paxdiablo 1. 正如Kobi所说：这个问题更多的是理论性质，而不是实际应用。我不知道任何地方会使用a^n b^n c^n，它只是理论。 - NikiC

1

你如何实现可读性是可以讨论的，我对此没有任何问题。也许使用一个更简单的正则表达式并检查捕获组长度会更容易理解。我写了一个“正确”的解析器（尽管比绝对必要的更复杂），因为考虑到我的背景，这对我来说是一个相当容易的任务。我的观点不是我所写的是理想答案，而是在大多数情况下，你应该优先考虑可读性而不是“聪明才智” :-) - paxdiablo

1

不要忘记，在几乎所有的正则表达式引擎中，您都可以让空格无关紧要，因此可以在任何地方插入换行和注释来提高可读性。 - Brandon

显示剩余7条评论

5

Qtax技巧

有一个未被提及的解决方案：

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

在正则表达式演示中查看匹配和失败的内容。

这使用了自引用组（@Qtax在他的垂直正则表达式上使用的一个想法）。

- zx81

1

@Unihedron 是的，看到了，但他在这里的解决方案使用平衡组(.NET)，而这个则使用自引用组(Perl, PCRE)。完全不同的东西——但当然你从行号问题中已经知道了 :) - zx81

呵呵，"Qtax trick"，谢谢，但我必须要把这种技巧的功劳归给polygenelubricants。我是从他出色的正则表达式问题和答案中学到了这个技巧，比如如何使用Java正则表达式匹配a^n b^n？。 - Qtax

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

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

- NikiC · Accepted Answer

受NullUserExceptions答案的启发（他已经删除了它，因为它在一个案例中失败了），我认为我自己找到了一个解决方案：

$regex = '~^
    (?=(a(?-1)?b)c)
     a+(b(?-1)?c)
$~x';

var_dump(preg_match($regex, 'aabbcc'));    // 1
var_dump(preg_match($regex, 'aaabbbccc')); // 1
var_dump(preg_match($regex, 'aaabbbcc'));  // 0
var_dump(preg_match($regex, 'aaaccc'));    // 0
var_dump(preg_match($regex, 'aabcc'));     // 0
var_dump(preg_match($regex, 'abbcc'));     // 0

请自行尝试：http://codepad.viper-7.com/1erq9v

解释

如果你考虑不带正向先行断言（(?=...) 部分）的正则表达式，你会得到以下内容：

~^a+(b(?-1)?c)$~

这个代码段只是检查了任意数量的a后面跟着相等数量的b和c。

但这并不能满足我们的语法要求，因为a的数量也必须相同。我们可以通过检查a的数量是否等于b的数量来确保这一点。这就是先行断言表达式 (a(?-1)?b)c 的作用:。必须加上c，以便我们不仅匹配b的一部分。

结论

我认为这个例子令人印象深刻地表明，现代正则表达式不仅能够解析非正则语法，甚至能够解析非上下文无关的语法。希望这将结束“你不能使用正则表达式做X，因为X不是正则的”这种毫无根据的说法。