正则锻炼: factorials

Question

_{This is an experimental new feature for StackOverlow: exercising your regex muscles by solving various classical problems. There is no one right answer, and in fact we should collect as many right answers as possible, as long as they offer educational value. All flavors accepted, but please document it clearly. As much as practical, provide testcases/snippets to demonstrate that the pattern "works".}

如何使用正则表达式确定数字 x 是否为阶乘？

奖励:如果模式可以确定x = n!，它也可以找到n吗？

Answer 1

Java，具有无限长度的lookbehind和嵌套引用(see also on 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);
      }
   }
}
}