查看正则表达式重复是否可以减少的算法

发布时间：2020-12-14 05:59:39 所属栏目：百科来源：网络整理

导读：我正在寻找一种算法,可以检查嵌套的正则表达式重复是否可以减少.假设解析正则表达式已经完成. 例： (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

我正在寻找一种算法,可以检查嵌套的正则表达式重复是否可以减少.假设解析正则表达式已经完成.

例：

(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}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!