C语言 解决正则表达式的匹配（递归思路）

解题思路（递归）

这里我们不妨假设有一个字符串aabc 以及一个匹配式：a*bc。按照递归的思想，我们的目的就是匹配完整的字符串，也就是第一个字符匹配成功 再匹配第二个字符 以此类推，直到匹配完成所有的字符。什么时候匹配结束呢？肯定某一个字符串为空 或者无法匹配的情况。因此进行以下情况的考虑：

1. case1：假设 表达式为空 匹配式也为空：显然匹配成功

2. case2：假设 表达式不为空，而匹配式为空：这种情况下显然 匹配失败。

3. case3：假设 表达式为空，而匹配式不为空：在这种情况下针对匹配式又有两种小的可能：

   ·case3.1 如果匹配式的样式为 a*b*a*c*这种字母和*成对出现的情况，显然可以进行规约的，因此可以先判断是否偶数个字符，再根据*舍弃前两个字符进行递归，最终会递归到case1的情况，说明匹配成功。

4. case4：假设 表达式不为空 匹配式也不为空：这种情况下，由于匹配式中*的存在，造成干扰，需要分两种情况来考虑：

   ·case4.1 假设匹配式的第二个字符不是*，这样说明匹配式的第一个字符固定了，直接和表达式第一个字符比较，然后都右移一位递归即可。

   ·case4.2：假设匹配式的第二个字符是*，如果第一个字符能匹配上说明：匹配式可以抵消前两个字符，也可以单方面抵消表达式的一个字符，因此可以做一个或运算的递归。如果匹配不上，说明匹配式只能舍弃前两个字符，再进行递归。

注意

判断表达式和匹配式的一个字符是否匹配的时候，如果匹配式是'.'，直接能匹配上。例如aaa a.a

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @param pattern string字符串 
 * @return bool布尔型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
//一个递归的方式 从前到后进行字符串匹配
bool match_str(char *str, char *pattern){
    //递归的终止条件 某个字符串为空
    //1. 都为空 明显匹配成功
    int a;
    if(*str=='\0'&&*pattern=='\0')
        return true;
    //2. pattern为空 str不为空 明显匹配失败
    else if(*str!='\0'&&*pattern=='\0')
        return false;
    //3. str为空 pattern 不为空,这个时候 只有形如 a*b*c*的才能匹配成功 否则匹配失败
    //可以继续递归 抵消一对 a*
    else if(*str=='\0'&&*pattern!='\0')
    {
        //必须偶数个
        if(strlen(pattern)%2==0){
            //判断前两个字符是否为 a*样式
            if(pattern[0]!='*'&&pattern[1]=='*')
                //抵消两个字符后递归
                return match_str(str,&pattern[2]);
            else
                return false;
        }
        else 
            return false;
    }
    //4. 两个字符串都不为空 考虑pattern的第二个字符是否为*
    else{
        //4.1 pattern的第二个字符不是* 说明只有第一个字符匹配才能进行递归
        if(pattern[1]!='*'){
            //第一个字符匹配成功 均右移一个字符匹配
            if(str[0]==pattern[0]||pattern[0]=='.')
                return match_str(&str[1], &pattern[1]);
            //第一个字符匹配失败 返回失败
            else
                return false;
        }
        // pattern的第二个字符是 * 此时判断第一个字符是否匹配 
        else{
            //第一个字符也匹配上了 说明可以舍弃匹配式的两个字符 也可以舍弃一个字符串的字符
            if(str[0]==pattern[0]||pattern[0]=='.')
                return (match_str(&str[0], &pattern[2])||match_str(&str[1], &pattern[0]));
            //说明第一个字符没有匹配上 这时候必须舍弃掉匹配式的前两个字符b* 
            else{
                 return match_str(str, &pattern[2]);
            }
                
        }
        
        
    }
}
bool match(char* str, char* pattern ) {
    // write code here
    if(str==NULL||pattern==NULL)
        return false;
    return match_str(str,pattern);
    
}