正则表达式 - 匹配任何重复n次的字符

16

如何匹配重复出现n次的任意字符?

示例:

for input: abcdbcdcdd
for n=1:   ..........
for n=2:    .........
for n=3:     .. .....
for n=4:      .  . ..
for n=5:   no matches

几个小时后,我最好的表达是这个。

(\w)(?=(?:.*\1){n-1,}) //where n is variable

这个表达式使用了向前查看。然而,这个表达式的问题在于:

for input: abcdbcdcdd
for n=1    .......... 
for n=2     ... .. .
for n=3      ..  .
for n=4       .
for n=5    no matches

正如您所看到的,当前瞻匹配到一个字符时,让我们看一下n=4行,d的当前瞻断言被满足并且第一个d被正则表达式匹配。但是其余的d因为它们没有3个以上的d在它们之前而没有被匹配。

我希望我清楚地说明了问题。期待您的解决方案,提前致谢。

4个回答

8
让我们寻找 n=4 行,d 的 lookahead 断言得到满足,并且第一个 d 被正则表达式匹配。但是剩余的 d 没有被匹配,因为它们前面没有 3 个以上的 d。很明显,没有正则表达式,这是一个非常简单的字符串操作问题。我正在尝试只使用正则表达式来解决这个问题。
与任何正则表达式实现一样,答案取决于正则表达式的风格。你可以使用 正则表达式引擎创建一个解决方案,因为它允许可变宽度的 lookbehinds。
此外,我将在下面提供一个更通用的解决方案,适用于 perl 兼容/类似的正则表达式风格。

.net解决方案

正如@PetSerAl在他的答案中所指出的那样,使用可变宽度的前后断言,我们可以断言回到字符串的开头,并检查是否有n个出现。
ideone演示

Python中的regex模块
您可以在中实现此解决方案,使用Matthew Barnett的regex模块,该模块还允许使用可变宽度的前后断言。

>>> import regex
>>> regex.findall( r'(\w)(?<=(?=(?>.*?\1){2})\A.*)', 'abcdbcdcdd')
['b', 'c', 'd', 'b', 'c', 'd', 'c', 'd', 'd']
>>> regex.findall( r'(\w)(?<=(?=(?>.*?\1){3})\A.*)', 'abcdbcdcdd')
['c', 'd', 'c', 'd', 'c', 'd', 'd']
>>> regex.findall( r'(\w)(?<=(?=(?>.*?\1){4})\A.*)', 'abcdbcdcdd')
['d', 'd', 'd', 'd']
>>> regex.findall( r'(\w)(?<=(?=(?>.*?\1){5})\A.*)', 'abcdbcdcdd')
[]


通用解决方案

或任何“类似perl”的变体中,没有一种解决方案可以实际返回每个重复字符的匹配,但我们可以为每个字符创建一个且仅一个捕获

策略

对于任何给定的n,逻辑涉及:

  1. 早期匹配:匹配并捕获后面至少出现n次的每个字符。
  2. 最终捕获:
    • 匹配并捕获一个字符,后面紧跟着恰好出现n-1次,以及
    • 也捕获以下每个出现。

示例

for n = 3
input = abcdbcdcdd

字符c仅匹配一次(作为最终匹配),接下来的2次出现也在同一匹配中捕获
abcdbcdcdd
  M  C C

并且字符d在 (早期) 匹配时仅匹配一次:

abcdbcdcdd
   M

最后,匹配成功,并捕获了剩余的部分:

abcdbcdcdd
      M CC

正则表达式

/(\w)                        # match 1 character
(?:
    (?=(?:.*?\1){≪N≫})     # [1] followed by other ≪N≫ occurrences
  |                          #   OR
    (?=                      # [2] followed by:
        (?:(?!\1).)*(\1)     #      2nd occurence <captured>
        (?:(?!\1).)*(\1)     #      3rd occurence <captured>
        ≪repeat previous≫  #      repeat subpattern (n-1) times
                             #     *exactly (n-1) times*
        (?!.*?\1)            #     not followed by another occurence
    )
)/xg

对于n =

  1. /(\w)(?:(?=(?:.*?\1){2})|(?=(?:(?!\1).)*(\1)(?!.*?\1)))/g
    演示
  2. /(\w)(?:(?=(?:.*?\1){3})|(?=(?:(?!\1).)*(\1)(?:(?!\1).)*(\1)(?!.*?\1)))/g
    演示
  3. /(\w)(?:(?=(?:.*?\1){4})|(?=(?:(?!\1).)*(\1)(?:(?!\1).)*(\1)(?:(?!\1).)*(\1)(?!.*?\1)))/g
    演示
  4. ...等等。
生成该模式的伪代码
// Variables: N (int)

character = "(\w)"
early_match = "(?=(?:.*?\1){" + N + "})"

final_match = "(?="
for i = 1; i < N; i++
    final_match += "(?:(?!\1).)*(\1)"
final_match += "(?!.*?\1))"

pattern = character + "(?:" + early_match + "|" + final_match + ")"

JavaScript 代码

我将展示一个使用 实现的例子,因为我们可以在这里检查结果(如果它在 JavaScript 中起作用,则它在任何兼容 perl 的正则表达式中都有效,包括 , , , , ,以及所有实现了 的语言等)。

var str = 'abcdbcdcdd';
var pattern, re, match, N, i;
var output = "";

// We'll show the results for N = 2, 3 and 4
for (N = 2; N <= 4; N++) {
    // Generate pattern
    pattern = "(\\w)(?:(?=(?:.*?\\1){" + N + "})|(?=";
    for (i = 1; i < N; i++) {
        pattern += "(?:(?!\\1).)*(\\1)";
    }
    pattern += "(?!.*?\\1)))";
    re = new RegExp(pattern, "g");
    
    output += "<h3>N = " + N + "</h3><pre>Pattern: " + pattern + "\nText: " + str;
    
    // Loop all matches
    while ((match = re.exec(str)) !== null) {
        output += "\nPos: " + match.index + "\tMatch:";
        // Loop all captures
        x = 1;
        while (match[x] != null) {
            output += " " + match[x];
            x++;
        }
    }
    
    output += "</pre>";
}

document.write(output);

Python3 代码

根据 OP 的要求,我链接到一个ideone.com 上的 Python3 实现


非常感谢您提供的信息丰富的答案!因此,解决方案似乎是使用强大的正则表达式语法,其中可以在一个中使用前瞻和后顾。我想知道在Python3中是否可能实现。因为我整晚都在尝试 :) - Ferit

7
正则表达式(以及有限自动机)不能将数字计数到任意整数。它们只能计数到预定义的整数,幸运的是,这是你的情况。
如果我们首先构建一个非确定性有限自动机(NFA),然后将其转换为正则表达式,解决这个问题会更容易。
所以当n=2且输入字母表={a,b,c,d}时,下面的自动机 enter image description here 将匹配具有恰好2个重复字符的任何字符串。如果没有字符重复两次(所有字符出现少于或多于两次),则该字符串不匹配。
将其转换为正则表达式应如下所示:
"^([^a]*a[^a]*a[^a]*)|([^b]*b[^b]*b[^b]*)|([^b]*c[^c]*c[^C]*)|([^d]*d[^d]*d[^d]*)$"

如果输入的字母表很大,这可能会变得棘手,因此正则表达式应该以某种方式缩短,但我现在想不出来。


感谢您提供的信息丰富的答案!构建NFA是解决正则表达式问题的好方法,它让我想起了我在大学学习的形式语言和自动机课程。然而,正如您所说,这个正则表达式非常长,不可行,我们应该找到一个更短的解决方案。因此,我会给您点赞,但不会将其标记为已接受的答案。 - Ferit
谢谢您的回答。我需要的是自动机解决方案,而不是编程语言的解决方案。 - Maubeh

4

.NET正则表达式可以实现以下功能:

(\w)(?<=(?=(?:.*\1){n})^.*) where n is variable

Where:

  • (\w) — 表示任意字符,且该字符在第一个组中被捕获。
  • (?<=^.*) — 向前查找断言,将我们返回到字符串的开头。
  • (?=(?:.*\1){n}) — 向后查找断言,用于查看字符串中是否有n个该字符的实例。

演示


感谢您的回答,我已经点赞了。但是,Mariano的回答更好,所以我将他的回答标记为已接受。看起来解决这个问题的方法是使用非常强大的正则表达式语法,其中可以在一个中使用lookbehinds和lookaheads。我想知道,在Python3中是否可能实现这一点。 - Ferit
1
@Saibot 这确实是一个出色的解决方案,但并不一定直观。所有“类 Perl”风格的正则表达式都允许嵌套环视,问题在于如何支持像 (?<=^re.*) 这样的可变宽度回顾后发断言。你可以在Python中使用外部模块来实现这个功能。Matthew Barnett开发的regex模块也允许可变宽度的回顾后发断言。 - Mariano

3

我不会使用正则表达式来完成这个任务,我会使用像Python这样的脚本语言。请尝试使用下面这个Python函数:

alpha = 'abcdefghijklmnopqrstuvwxyz'
def get_matched_chars(n, s):
    s = s.lower()
    return [char for char in alpha if s.count(char) == n]

该函数将返回一个字符列表,其中所有字符在字符串s中恰好出现n次。请注意,我在我的字母表中只包括字母。您可以更改alpha以表示您想要匹配的任何内容。

谢谢回答,但我们都知道如何在没有正则表达式的情况下完成。显然,没有正则表达式,这是一个非常简单的字符串操作问题。我正在尝试仅使用正则表达式来解决这个问题。 - Ferit

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接