正则表达式：以任意顺序匹配特定字符，每个字符的出现次数不超过指定次数

Question

我有一个字符列表，例如

{o, b, c, c, d, o, f}

。

如果字符串包含不在该列表中的字符，我不希望它成为匹配项。如果一个字符串包含的某个字符的出现次数多于该列表中该字符的出现次数，我不希望它成为匹配项。

字符串中的字符可以以任意顺序出现，并且不必所有字符都出现。在上面的示例中，

"foo"

应该是匹配项，但不是

"fooo"

。

例如，我将上面的示例缩小为

(o{0,2}b?c{0,2}d?f?)

，但这并不完全有效，因为该正则表达式中的顺序很重要。我得到了

"oof"

的匹配，但没有

"foo"

的匹配。

Answer 1

正如 gview 所说，正则表达式不是正确的工具。但是，如果您的正则表达式引擎支持前瞻，您可以使用这个：

^(?=(?:[^o]*o){0,2}[^o]*$)(?=(?:[^c]*c){0,2}[^c]*$)(?=[^b]*b?[^b]*$)(?=[^d]*d?[^d]*$)(?=[^f]*f?[^f]*$)[obcdf]+$

有点长但很简单：

字符串与

^[obcdf]+$

匹配（注意锚点的使用）。

前瞻

(?=...)

只是检查（后面跟着）：

(?=(?:[^o]*o){0,2}[^o]*$)   # no more than 2 o until the end

(?=[^b]*b?[^b]*$) # no more than 1 b until the end

lookaheads 中的每个子模式都描述整个字符串。

Answer 2

我认为正则表达式不是满足该要求的正确工具。 我将创建一个简单的数组，其中包含白名单中的字符计数。 如果您的语言具有关联数组，则按字母键入并获取数组元素中出现的次数。

然后逐个字符处理单词，尝试在关联数组中进行匹配，并减少可用计数。

如果出现以下任一情况，则失败：

• 数组中没有匹配的字母
• 您匹配，但匹配的字母已没有剩余计数。

Answer 3

另一种方法也可能有效

 # ^(?!(?:.*o){3})(?!(?:.*c){3})(?!(?:.*b){2})(?!(?:.*d){2})(?!(?:.*f){2})[obcdf]+$

 ^                 # BOS
 (?! (?:.* o){3} ) # not more than 2 'o'
 (?! (?:.* c){3} ) # not more than 2 'c'
 (?! (?:.* b){2} ) # not more than 1 'b'
 (?! (?:.* d){2} ) # not more than 1 'd'
 (?! (?:.* f){2} ) # not more than 1 'f'
 [obcdf]+          # can only be these
 $                 # EOS

Answer 4

顺序的交替（也称为交错）是并行执行的典型方面。本质上，正则表达式是表示非确定性有限自动机 (NFA) 的一种形式。 能够有效编码交错语义的自动机称为并行有限自动机（PFA）。好消息：PFA 明显等同于 NFA 和 DFA。请参阅著作《并行有限自动机用于并行软件系统建模》，它证明了这种等价性，并提供了将 PFA 转换为 DFA 的算法，以及交错表达式的类似正则表达式的语法。 在该语法中，您的模式被编码为 (o||o||b||c||c||d||f)。 参考论文中提供的算法从任何 PFA 构造 NFA，从而允许人们将交错的正则表达式重写为“正常”正则表达式，尽管它可能有点长而不舒服。