题解 | #正则表达式匹配#
正则表达式匹配
http://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4
C语言 解决正则表达式的匹配(递归思路)
解题思路(递归)
这里我们不妨假设有一个字符串aabc 以及一个匹配式:a*bc。按照递归的思想,我们的目的就是匹配完整的字符串,也就是第一个字符匹配成功 再匹配第二个字符 以此类推,直到匹配完成所有的字符。什么时候匹配结束呢?肯定某一个字符串为空 或者无法匹配的情况。因此进行以下情况的考虑:
-
case1:假设 表达式为空 匹配式也为空:显然匹配成功
-
case2:假设 表达式不为空,而匹配式为空:这种情况下显然 匹配失败。
-
case3:假设 表达式为空,而匹配式不为空:在这种情况下针对匹配式又有两种小的可能:
·case3.1 如果匹配式的样式为 a*b*a*c*这种字母和*成对出现的情况,显然可以进行规约的,因此可以先判断是否偶数个字符,再根据*舍弃前两个字符进行递归,最终会递归到case1的情况,说明匹配成功。
-
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);
}