regex - 请帮助一些正则表达式

Question

我在看龙书，被一些正则表达式练习卡住了，很有趣，有人能帮忙吗？请为以下语言编写正则表达式：

问题 1：
a 和 b 的所有字符串具有偶数个 a 和奇数个 b。

问题2：
所有不包含子序列abb的字符串。（s 的子序列是通过删除零个或多个不一定连续的 seg 位置形成的任何字符串 baan 是香蕉的子序列。）

问题3：
所有没有重复数字的数字串（重复数字不一定是连续的）。

问题4：
最多有一个重复数字的所有数字串（重复数字不一定是连续的）。

并且请使用 POSIX 语法，以便我们都能很好地理解它。另外我想知道我们是否只能使用三种基本的语言操作，即联合、连接和闭包来实现它们？

谢谢。

score 0 · Accepted Answer

如果您有严格的正则表达式（连接、联合、闭包），您将能够将其转换为 POSIX 正则表达式。如果您有 POSIX 正则表达式，您将能够将其转换为任何更复杂的正则表达式引擎。

假设（请先阅读此内容）

这个答案假设了 JavaScript 正则表达式的支持级别（有前瞻但没有后瞻），但我们也假设.匹配任何字符无异常。这里的正则表达式将假定整个字符串与模式匹配。

问题 1

^(?=(?:b*ab*a)*b*$)(?=(?:a*ba*b)*a*ba*$)[ab]*$

可以为这个问题构造一个 DFA，因此，存在一个只有连接、联合和闭包的正则表达式。（DFA 中状态中的数字表示 a 和 b 的数量的奇偶性）。

DFA 问题 1

然而，严格的正则表达式的推导相当混乱；环顾四周简化了我们的思考方式。

(?=(?:b*ab*a)*b*$)是一个前瞻，（由于^and的影响$）检查整个字符串是否匹配(b*ab*a)*b*- 这意味着偶数个a's，b在两者之间和周围有可选的和有限的多个。
(?=(?:a*ba*b)*a*ba*$)是一个前瞻，检查整个字符串是否匹配(a*ba*b)*a*ba*- 这意味着奇数个b's，a在两者之间和周围可选且有限多个。

我们将需要 3 次遍历字符串来检查字符串是否满足上述正则表达式的给定属性。

使用 POSIX 正则表达式，您可以针对这 2 个正则表达式测试字符串 2 次以断言 2 个属性：

^(b*ab*a)*b*$
^(a*ba*b)*a*ba*$

但是由于存在严格的正则表达式并且可行，因此存在单个 POSIX 正则表达式来匹配满足属性的字符串。请阅读这篇文章了解将 DFA 转换为严格正则表达式的方法。

问题 2

^(?!.*a.*b.*b).*$

只是向前看，检查没有办法匹配 subsequence abb。

由于没有指定字母表，可以将其解释为存在的任何和所有字符，因此用严格的正则表达式编写它是可能的，但不切实际。但是，如果允许否定字符类，则可以轻松编写：

([^a]*a[^b]*b[^b]*|[^a]*a[^b]*|[^a]*)

（上面是严格的正则表达式，但是可以很容易地改写为POSIX正则表达式）

DFA 问题 2

交替的 3 个项目（从右到左）对应于 DFA 中的 3 个状态：尚未找到a；有一个a，但没有b前面；有一个a，b然后在某处之后，但还没有找到第二个b。在 DFA 中还有另一个陷阱状态（不可能转换到目标状态）：abb已经找到子序列。

问题 3

^(?!\d*(\d)\d*\1)\d+$

使用负前瞻，我们将只检查是否没有匹配项可以找到重复的字符。由于这是一个数字字符串，因此我不允许通过指定至少 1 个数字来匹配空字符串\d+。此正则表达式的关键点是使用捕获的组和反向引用。

同样，对此存在严格的正则表达式，但这是不切实际的，因为编写这样的正则表达式几乎等同于一一列出所有可能的匹配项。总共有Sum [i = 1..10] ( 10! / i! )可能的匹配项（允许前导 0）。没有办法绕过它，因为是否允许下一个字符在很大程度上取决于到目前为止已处理的所有字符。

这在 POSIX 正则表达式中也是不切实际的，因为没有否定捕获组的机制。

问题 4

无法为这个想出更好的正则表达式......

^(?!(?=.*(.).*\1).*((?!\1).).*\2)(?!.*(.)(?:.*\3){2})\d+$

失败有 2 个条件：数字重复超过 2 次，或者有 2 个不同的数字重复。

(?!(?=.*(.).*\1).*((?!\1).).*\2)检查是否有 2 个不同的数字重复。由于，这种前瞻(?=.*(.).*\1)选择了一个重复的字符（至少两次），并.*((?!\1).).*\2选择了一个与之前检查的不同的数字((?!\1).)，并尝试找到重复的数字。
(?!.*(.)(?:.*\3){2})检查一个数字最多重复两次。里面的模式尝试匹配一个数字的 3 个实例。

这与问题 3 有相同的问题，因此编写严格的正则表达式或 POSIX 正则表达式是不切实际的。如果您好奇，Sum [i = 1..10] ( 10! / i! ) + Sum [i = 1..10] ( (i + 1)C2 * 10! / i! )可能会有匹配项（允许前导 0）。

对于问题 3 和 4，尤其是问题 4，更实际的做法是检查字符串是否仅包含数字，然后对数字进行排序并遍历它以检查重复的数字。

1 回答 1