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

regex java c# capturing-group nested-reference

2022-09-01 01:10:14

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

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

有许多方法可以检查数字是否为三角形。有一个有趣的技术，它使用正则表达式，如下所示：

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

以下是一些片段，表明这适用于多种语言：

菲律宾比索（ideone.com）

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

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

爪哇（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);
    }
}

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

类似问题

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

答案 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 正则表达式中，您实际上可以获得由重复捕获组进行的所有中间捕获。在大多数风格中，你不能：所有的中间捕获都丢失了，你只能保留最后一个。

奖励材料：使用正则表达式来查找二进制的力量!!!

通过非常轻微的修改，您可以使用此处介绍的相同技术来查找二的力量。

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

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|^.)*.$}}}

答案 2