首页 文章

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

提问于
浏览 次
40

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

前几个triangular numbers是：

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

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

类似的问题

c# java regex capturing-group nested-reference

1 回答

  • 35

    解释

    这是模式的示意性细分：

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

    (…) brackets定义捕获组1，此组为matched repeatedly，其中包含 + . 此子模式为anchored，带有 ^ 和 $ ，以查看它是否可以匹配整个字符串 .

    第1组尝试匹配 this|that alternates：

    • \1. ，即1组匹配（自引用！），加上"any" character之一，

    • 或 ^. ，也就是说，开头只有"any"一个字符

    请注意，在第1组中，我们引用了第1组匹配的内容！这是嵌套/自引用，是本示例中介绍的主要思想 . 请记住，当重复捕获组时，通常it only keeps the last capture，因此在这种情况下自我引用基本上是这样的：

    “尝试匹配我上次匹配的内容，再加上一次 . 这就是我这次匹配的内容 . ”

    与递归类似，必须有一个带有自引用的"base case" . 在 + 的第一次迭代中，组1还没有捕获任何东西（这与说它以空字符串开始时不同） . 因此，引入第二个替换，作为组1的一种方式，即它在字符串的开头是's allowed to capture one character when it' .

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

    进一步探索

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

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

    这两点都显示在以下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，你正在询问与正则表达式相关的问题 .

    在大多数情况下，标准正则表达式匹配机制会尝试查看模式是否可以匹配输入字符串的任何部分（可能，但不一定是整个输入） . 这意味着您应该记住在必要时始终使用 ^ 和 $ 锚定您的模式 .

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

    请注意，在其他上下文中，您可能需要使用 \A 和 \Z 锚点 . 例如，在multiline mode中， ^ 和 $ 匹配输入中每行的开头和结尾 .

    最后一点是，在.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

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

    （参见ideone.com inPHP，Java和C＃）：^（\ 1 \ 1 | ^ . ）* . $

    回复于

相关问题