Thursday, September 16, 2010

Finding factorials using regex: .NET balancing groups

Believe it or not, this is also a first iteration solution. In fact, as a personal first, this pattern was completely developed on paper (see also on 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);
   }
}
The only thing that tripped me up was the need for reluctant quantifier, but everything else was exactly as it was first written on paper.
I'm halfway convinced that the problem with the greedy repetition is a bug, or perhaps was and has since been fixed (see: stackoverflow - Backtracking a balancing group in a greedy repetition may cause imbalance?)

No comments:

Post a Comment