这个正则expression式如何find三angular形数字?

作为一系列教育正则expression式文章的一部分,这是对嵌套引用的概念的一个温柔的介绍。

前几个三angular形数字是:

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

有很多方法来检查一个数字是否是三angular形的。 有这个有趣的技术,使用正则expression式如下:

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

以下是一些片段,可以显示出这种语言可以使用多种语言:

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

所以这个正则expression式似乎工作,但有人可以解释如何?

类似的问题

  • 如何确定一个数是否是正则expression式的一个主要元素?

说明

以下是该模式的示意图:

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

括号 (…) 括号定义了捕获组1,并且该组与+ 重复匹配 。 这个子模式用^$来锚定 ,看它是否可以匹配整个string。

组1试图匹配this|that 交替 :

  • \1. ,也就是什么组1匹配(自引用!),加上“任意”字符之一 ,
  • ^. 也就是说,一开始就是“任何”一个字

请注意,在第1组中,我们参考了第1组匹配的内容! 这是一个嵌套/自我引用 ,是本示例中介绍的主要思想。 请记住,当一个捕获组被重复时,通常它只保留最后一次捕获 ,所以在这种情况下,自我引用基本上是这样说的:

“试着匹配我上次匹配的,再加上一个,这次我会匹配。

类似recursion,必须有一个“基本情况”与自我引用。 在+的第一次迭代中,组1还没有捕获任何东西(这等于说它以空string开头)。 因此引入了第二个交替,作为“初始化”组1的一种方式,即允许在string开始时捕获一个字符。

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


进一步的探索

请注意,为了简化,我们使用了与input相同重复字符的string。 现在我们知道这个模式是如何工作的,我们可以看到这个模式也可以匹配"1121231234""aababc"等string。

还要注意的是,如果我们发现n是一个三angular形数,即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) 

风味笔记

并不是所有的风格都支持嵌套的引用。 一定要熟悉你正在使用的风味的怪癖 (因此,当你要求提供与正则expression式相关的问题时,几乎总能帮助你提供这些信息)。

在大多数情况下,标准的正则expression式匹配机制试图查看一个模式是否可以匹配inputstring的任何部分 (可能但不一定是整个input)。 这意味着你应该记得在任何需要的时候始终使用^$来定位你的模式。

Java稍有不同, String.matchesPattern.matchesMatcher.matches尝试匹配整个inputstring的模式。 这就是为什么在上面的代码片段中可以省略锚点的原因。

请注意,在其他情况下,您可能需要使用\A\Z锚。 例如,在多行模式下 , ^$匹配input中每行的开始和结束。

最后一件事情是,在.NET正则expression式中,您实际上可以获得重复捕获组所做的所有中间捕获。 在大多数口味中,你不能:所有的中间捕捉都丢失了,你只能保持最后的。

相关问题

  • (Java)方法匹配效果不佳 – 例如如何做前缀/后缀/中缀匹配
  • 有没有一个正则expression式的味道,让我可以计算*+ (.NET!) 匹配的重复次数

奖金材料:使用正则expression式来发现两个力量!

通过非常微小的修改,您可以使用这里介绍的相同技术来find两个方面的力量。

以下是您想要利用的基本math属性:

  • 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

解决scheme如下(但尝试自己解决它!!!!)

(请参阅PHP , Java和C#中的 ideone.com):

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