正则练习：阶乘

Question

_{这是 StackOverlow 的一个实验性新功能：通过解决各种经典问题来锻炼你的正则表达式能力。没有唯一正确的答案，事实上我们应该收集尽可能多的正确答案，只要它们具有教育价值。接受所有口味，但请清楚记录。尽可能提供测试用例/片段来证明该模式“有效”。}

我们如何使用正则表达式查找数字x是否是阶乘？

额外奖励：如果模式可以确定x = n！，它也可以找到n吗？

Answer 1

Java，具有无限长度的后向查找和嵌套引用（另请参阅 ideone.com）：

import java.util.regex.*;

class Factorial {
static String assertPrefix(String pattern) {
   return "(?<=(?=^pattern).*)".replace("pattern", pattern);
}
public static void main(String[] args) {
   final Pattern FACTORIAL = Pattern.compile(
      "(?x) (?: inc stepUp)+"
         .replace("inc", "(?=(^|\\1 .))")
         //                      1

         .replace("stepUp", "(?: ^. | (?<=(^.*)) (?=(.*)) (?: notThereYet \\2)+ exactlyThere )")
         //                                2          3

         .replace("notThereYet", "(?:  (?=((?=\\3) .  |  \\4 .)) (?=\\1(.*)) (?=\\4\\5)  )")
         //                                           4                  5

         .replace("exactlyThere", "measure4 measure1")
            .replace("measure4", assertPrefix("\\4(.*)"))
            .replace("measure1", assertPrefix("\\1\\6"))
   );

   for (int n = 0; n < 1000; n++) {
      Matcher m = FACTORIAL.matcher(new String(new char[n]));
      if (m.matches()) {
         System.out.printf("%3s = %s!%n", n, m.group(1).length() + 1);
      }
   }
}
}

Answer 2

使用 C# 中的 .NET 平衡组（另请参阅 ideone.com）：

var r = new Regex(@"(?xn) 

^(
   (
     ( ^.
     | (?=  (?<temp-n> .)+ )
       (?<= (?<fact>  .+)  )
       (?<n-temp> \k<fact> )+?
       (?(temp) (?!))
     )
     (?<n>)
   )+
 )$

");

for (int x = 0; x < 6000; x++) {
   Match m = r.Match("".PadLeft(x));
   if (m.Success) {
      Console.WriteLine("{0,4} = {1}! ", x, m.Groups["n"].Captures.Count);
   }
}

注意：

.NET 的版本ideone.com 使用的平衡组似乎有一个错误，导致上面的代码片段中不得不重复 +? 。在较新的版本中，简单的贪婪 + 可能就足够了。另请参阅：回溯平衡组贪婪重复可能会导致不平衡？