失败的经历：

1.想用循环来实现，发现基本不可能啊。

2.想用NFA->DFA实现，还是算了吧，又不是真的实现正则表达式引擎。

建议先自己实现，我这边有testCase可以测试，一边调试一边找错，会发现最后的实现很不错。啥都不说了，上代码。

本题目我最招是从coding_interview上看到的，这本书也很是不错。

// How do you implement a function to match regular expressions with ‘.’ and ‘*’ in patterns? The // character ‘.’ in a pattern matches a single character,and ‘*’ matches zero or any number of characters preceding // it. Matching means that a string fully matches the pattern where all characters in a string match the whole pattern. // For example,the string “aaa” matches the pattern “a.a” and the pattern “ab*ac*a”. However,it does not match // the pattern “aa.a” nor “ab*a”. #include <stdio.h> #include <assert.h> bool match(char* myString,char* pattern){ if(myString == NULL || pattern == NULL){ return false; } if(*myString != '\0' && *pattern != '\0'){ if(pattern[1] == '*'){ // this recursive can't be replaced by loop,they work together and coordinate complicatedly if(*myString == *pattern || *pattern == '.'){ return match(myString,pattern + 2)//skip * || match(myString + 1,pattern + 2)//eat a ch and skip * || match(myString + 1,pattern)//stay at current parrtern ; } else{ return match(myString,pattern + 2);//skip * } } else{ if(*myString == *pattern || *pattern == '.'){ return match(myString + 1,pattern + 1); } else{ return false; } } }//for if(*myString != '\0' || *pattern != '\0'){ return false; } return true; } //test case 0. NULL,a.a //test case 0. NULL,NULL //test case 0. aaa,NULL //test case 1. aaa,a.a //test case 1. aaa,a.*a //test case 2. aaa,ab*ac*a //test case 3. aaa,aa.a //test case 4. aaa,ab*a //test case 4. aaa,. //test case 4. aaa,*//invalid //test case 4. aaa,.* //test case 4. aaa,a.* //test case 4. aaa,a* void testCase0(){ bool result = match(NULL,"a.a"); assert(!result); result = match(NULL,NULL); assert(!result); result = match("aaa","a.a"); assert(result); result = match("aaa","a.*a"); assert(result); result = match("aaa","ab*ac*a"); assert(result); result = match("aaa","aa.a"); assert(!result); result = match("aaa","ab*a"); assert(!result); result = match("aaa","."); assert(!result); result = match("aaa","*"); assert(!result); result = match("aaa",".*"); assert(result); result = match("aaa","a.*"); assert(result); result = match("aaa","a*"); assert(result); } int main(){ testCase0(); }