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

Question

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

c#javaregexcapturing-groupnested-reference

44

_{本系列正则表达式文章的一部分，是对嵌套引用概念的简要介绍。}

 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);
    }
}

这个正则表达式似乎可以工作，但有人能解释一下吗？

类似的问题

如何使用正则表达式确定一个数字是否为质数？

- polygenelubricants

5

这个系列的开展得到了社区中一些人的许可 (http://meta.stackexchange.com/questions/62695/permission-to-start-a-series-of-advanced-regex-articles)。如果反响良好，我计划继续涵盖其他更高级和基础的正则表达式特性。 - polygenelubricants

1

如果这是为了教育和社区而设计的，为什么不是社区维基呢？ - wheaties

15

我认为付出一些声誉是值得的。请不要强制将它们放入社区维基中。谁在乎poly从44k变成50k有什么区别？ - jjnguy

3

我期待着这个系列。请注意，如果您对正则表达式的起源有兴趣，我曾经开始撰写一系列博客。不幸的是，我没有完成它。链接为：http://blogs.msdn.com/b/ericlippert/archive/tags/regular+expressions/。 - Eric Lippert

2

如果这是一个系列的话，那么怎么样发明一个标签，以简化查找该系列的所有“文章”呢？ - Andreas Dolk

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- polygenelubricants · Accepted Answer

解释

这是模式的示意图解：

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

(...) 括号定义捕获组1，这个组会通过+进行重复匹配。这个子模式会通过^和$进行锚定，以确定是否可以匹配整个字符串。

捕获组1尝试匹配this|that 交替的内容：

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