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

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组匹配的内容（自我参考！），加上“ any”字符之一，
• 或^.，即开头只是“任何”一个字符

请注意，在第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 真正得到通过重复捕获组的所有中间捕获。在大多数口味中，您不能：丢失所有中间捕获物，而只保留最后一个。

奖励材料：使用正则表达式查找二元幂！！！

经过非常小的修改，您就可以使用此处介绍的相同技术来找到二的力量。

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

• 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

解决方案如下（但请先尝试自己解决！！！）

（请参见ideone.com中的PHP，Java和C＃）：

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