这个正则表达式如何找到三角形数字？

Question

_{这是一系列教育正则表达式文章的一部分,这是对嵌套引用概念的温和介绍.}

前几个三角形数字是:

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

有很多方法可以检查数字是否为三角形.有一种有趣的技术使用正则表达式如下:

• 给定n,我们首先创建一个长度为n的字符串,其中填充相同的字符
• 然后我们将此字符串与模式匹配 ^(\1.|^.)+$
  • 当且仅当此模式与字符串匹配时,n为三角形

以下是一些片段,表明它适用于多种语言:

PHP(在ideone.com上)

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

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

Java(在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#(在ideone.com上)

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

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

所以这个正则表达式似乎有效,但有人可以解释一下吗？

类似的问题

• 如何确定一个数字是否是正则表达式的素数？

Answer 1

说明

这是模式的示意性细分:

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

所述(…) 托架限定捕获组1,而这个组被重复地匹配用+.此子模式使用和锚定,以查看它是否可以匹配整个字符串.^$

第1组尝试匹配this|that 替代项:

• \1.,也就是说,第1组匹配(自引用!),加上"任意"字符之一,
• 或者^.,也就是说,开头只是"任何"一个字符

请注意,在第1组中,我们引用了第1组匹配的内容!这是嵌套/自引用,是本示例中介绍的主要思想.请记住,当重复捕获组时,通常它只保留最后一次捕获,因此本例中的自引用基本上表示:

"尝试匹配我上次匹配的内容,再加上一次.这就是我这次匹配的内容."

与递归类似,必须有一个带有自引用的"基本案例".在的第一次迭代中+,第1组没有捕获任何东西(这是不是等于说,它开始与一个空字符串).因此,引入第二个替换,作为"初始化"组1的一种方式,即当它在字符串的开头时允许捕获一个字符.

因此,当重复时+,组1首先尝试匹配1个字符,然后是2,然后是3,然后是4,等等.这些数字的总和是三角形数字.

进一步的探索

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

另请注意,如果我们发现n是三角形数,即n = 1 + 2 + ... + k,则组1在末尾捕获的字符串的长度将为k.

这两点都显示在以下C#片段中(也可在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)

味道说明

并非所有口味都支持嵌套引用.始终熟悉您正在使用的风格的怪癖(因此,无论何时提出与正则表达式相关的问题,它几乎总是有助于提供此信息).

在大多数情况下,标准正则表达式匹配机制会尝试查看模式是否可以匹配输入字符串的任何部分(可能,但不一定是整个输入).这意味着,你要记得随时锚您的模式^,并$在必要时.

Java略有不同String.matches,Pattern.matches并Matcher.matches尝试将模式与整个输入字符串进行匹配.这就是为什么在上面的片段中可以省略锚点的原因.

请注意,在其他上下文中,您可能需要使用\A和\Z锚点.例如,在多行模式,^并且$匹配的开始和结束时的每一行中的输入.

最后一件事是,在.NET正则表达式,你CAN真正得到全部重复捕获组提出的中间捕获.在大多数风格中,你不能:所有中间捕获都丢失了,你只能保留最后一个.

相关问题

• (Java)方法匹配不正常 - 有关如何进行前缀/后缀/中缀匹配的示例
• 是否有正则表达式的味道,允许我计算匹配的重复次数*和+(.NET!)

奖金材料:使用正则表达式找到两个人的力量!

通过非常轻微的修改,您可以使用此处介绍的相同技术来查找二次方的功能.

这是您想要利用的基本数学属性:

• 1 = 1
• 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#中的 ideone.com ):

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