我正在寻找一种算法,可以检查嵌套的正则表达式重复是否可以减少.假设解析正则表达式已经完成.
例：
(1{1,2}){1,2} === 1{1,4}
It matches 1,11,111,1111 which can be rewritten as a single repeat
(1{2,2} can not be reduced
It matches 11 and 1111 which can not be rewritten as a single repeat.
(1{10,11}){1,2} can not be reduced
(1{10,19}){1,2} === 1{10,38}
(1{1,2}){10,11} === 1{10,22}
(1{10,11})* can not be reduced
(1*){10,11} === 1*
我一直试图找到这种类型的操作模式,而不必匹配所有可能的解决方案,并寻找可以防止它被减少的漏洞.必须有一个简单的函数(f(A,B,C,D) – >(E,F))可以解决任意输入,如下所示：
(1{A,B}){C,D} -> 1{E,F}
解决方法
// (x{A,D} -> x{E,F}
bool SimplifyNestedRepetition(int A,int B,int C,int D,out int E,out int F)
{
if (B == -1 || C == D || A*(C+1) <= B*C + 1)
{
E = A*C;
if (B == -1 || D == -1) F = -1;
else F = B*D;
return true;
}
return false;
}
>如果x {A,B}不受限制,则可以重复多次.
>(x {A,B}){C}总是可以减少的.
>如果A *(C 1)< = B * C 1,则可以减少它,因为C重复的最长序列与C 1重复的最短序列之间没有间隙.
B = -1或D == -1表示无限制,如x *或x {5,}.
测试用例：
Input Reducible?
(x{0,0}){0,0} Yes - x{0,0}
(x{0,1}){0,2}){0,0}
(x{1,3}){0,0}
(x{2,4}){0,1} Yes - x{0,1}
(x{0,2}
(x{1,1}
(x{1,3}
(x{2,1} No
(x{2,1} No
(x{0,2} Yes - x{0,2}
(x{0,4}
(x{1,6}
(x{2,2} No
(x{2,2} No
(x{0,0}){1,1}){1,1} Yes - x{1,3}){1,1} Yes - x{2,2}
(x{2,4}){1,4}
(x{0,2} Yes - x{1,2} Yes - x{2,8}
(x{0,3} Yes - x{0,3}
(x{0,6}
(x{1,3} Yes - x{1,3}
(x{1,9}
(x{2,3} No
(x{2,3} Yes - x{2,12}
(x{0,0}){2,1}){2,2}){2,3}){2,2} Yes - x{4,4}
(x{2,4}){2,3} Yes - x{4,4} Yes - x{0,8}
(x{1,4} Yes - x{2,12}
(x{2,4} No
(x{2,4} Yes - x{4,16}
