4

これは、StackOverlow の実験的な新機能です。さまざまな古典的な問題を解決することで、正規表現の筋肉を鍛えます。正しい答えは 1 つではありません。実際、正しい答えが教育的価値を提供する限り、できるだけ多くの正しい答えを収集する必要があります。すべてのフレーバーが受け入れられますが、明確に文書化してください。できるだけ実用的なテストケース/スニペットを提供して、パターンが「機能する」ことを実証します。

正規表現を使用して、数値xが階乗であるかどうかをどのように確認できますか?

おまけ: パターンがx = nと判断できる場合! 、 nも見つけることができますか？

4

2 に答える 2

3

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);
      }
   }
}
}
于 2010-09-20T01:05:35.507 に答える
1

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

ノート：

ideone.com で使用されている .NET のバージョンには、バランシング グループにバグがある+?ようで、上記のスニペットでの繰り返しが必要でした。新しいバージョンでは、単純な貪欲で+十分な場合があります。参照:貪欲な繰り返しでバランス グループをバックトラックすると、バランスが崩れる可能性があります。

于 2010-09-20T01:00:30.807 に答える