代码之家 › 专栏 › 技术社区 › polygenelubricants

这个正则表达式如何找到三角数?

nested-reference capturing-group regex java c#

41

polygenelubricants · 技术社区 · 15 年前

 1 = 1
 3 = 1 + 2
 6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4
15 = 1 + 2 + 3 + 4 + 5

鉴于 ,我们首先创建一个长度为 n 用相同的字符填充
然后我们将这个字符串与模式匹配 ^(\1.|^.)+$
- n

以下是一些代码片段,以说明这在几种语言中都是有效的:

PHP (on ideone.com)

$r = '/^(\1.|^.)+$/';

foreach (range(0,50) as $n) {
  if (preg_match($r, str_repeat('o', $n))) {
     print("$n ");
  }
}

Java (on ideone.com)

for (int n = 0; n <= 50; n++) {
    String s = new String(new char[n]);
    if (s.matches("(\\1.|^.)+")) {
        System.out.print(n + " ");
    }
}

C# (on ideone.com)

Regex r = new Regex(@"^(\1.|^.)+$");

for (int n = 0; n <= 50; n++) {
    if (r.IsMatch("".PadLeft(n))) {
       Console.Write("{0} ", n);
    }
}

所以这个正则表达式似乎起作用了,但是有人能解释一下它是怎么起作用的吗?

类似问题

How to determine if a number is a prime with regex?

1 回复 | 直到 8 年前

1

36

Community CDub 5 年前

解释

下面是模式的示意图:

from beginningâ¦
|         â¦to end
|         |
^(\1.|^.)+$
 \______/|___match
  group 1    one-or-more times

这个 (â¦) brackets 定义捕获组1,此组为 matched repeatedly 具有 + . 这个子模式是 anchored 具有 ^ 和 $ 看看它是否能匹配整个字符串。

第一组尝试匹配 this|that alternates :

\1. ,也就是说,第1组匹配的是什么(自我参照!),加上 "any" character
或 ^.

请注意,在第1组中,我们有一个与第1组匹配的参考!这是一个 嵌套/自引用 ,是本例中介绍的主要思想。请记住,当一个捕获组被重复时,通常 it only keeps the last capture ,所以这个例子中的自我参照基本上是这样的:

与递归类似,必须有一个带有自引用的“基本情况”。在 + 不是就像说它以一个空字符串开始一样)。因此引入了第二种替代方法,作为“初始化”组1的一种方法,即允许在字符串开头捕获一个字符。

因此,它是重复与 + ,组1首先尝试匹配1个字符,然后是2,然后是3,然后是4,以此类推。这些数字的和是一个三角形数字。

请注意,为了简化,我们使用了与输入相同的重复字符组成的字符串。现在我们知道了这个模式是如何工作的,我们可以看到这个模式也可以匹配字符串,比如 "1121231234" , "aababc"

还要注意,如果我们发现 n n=1+2++k ,组1在末尾捕获的字符串的长度将为

这两点都显示在下面的C代码片段中( also seen on ideone.com

Regex r = new Regex(@"^(\1.|^.)+$");

Console.WriteLine(r.IsMatch("aababc"));     // True
Console.WriteLine(r.IsMatch("1121231234")); // True
Console.WriteLine(r.IsMatch("iLoveRegEx")); // False

for (int n = 0; n <= 50; n++) {
    Match m = r.Match("".PadLeft(n));
    if (m.Success) {
       Console.WriteLine("{0} = sum(1..{1})", n, m.Groups[1].Length);
    }
}
// 1 = sum(1..1)
// 3 = sum(1..2)
// 6 = sum(1..3)
// 10 = sum(1..4)
// 15 = sum(1..5)
// 21 = sum(1..6)
// 28 = sum(1..7)
// 36 = sum(1..8)
// 45 = sum(1..9)

风味笔记

并非所有的风格都支持嵌套引用。经常熟悉 the quirks of the flavor

输入字符串(可能,但不一定,整个输入)。这意味着您应该记住始终用和 $ 必要时。

String.matches , Pattern.matches Matcher.matches 试图将一种模式与另一种模式相匹配 整个的 输入字符串。这就是为什么在上面的代码段中可以省略锚点。

\A 和 \Z multiline mode ^ 和 $ 每行在输入中。

最后一件事是在.NET正则表达式中实际获取重复捕获组所做的所有中间捕获。在大多数情况下,你不能:所有的中间捕获都丢失了,你只能保留最后一个。

奖励材料:使用正则表达式找到2的力量!!!

只要稍加修改,您就可以使用这里介绍的相同技术来查找二的幂。

下面是您要利用的基本数学特性:

1 = 1
4 = (1+2) + 1
8 = (1+2+4) + 1
16 = (1+2+4+8) + 1
32 = (1+2+4+8+16) + 1

下面给出了解决方案(但一定要先自己解决!!!!)

PHP , Java C# ):

^{^{^{^(\1\1|^.)*.$}}}