C语言正则表达式简单实现

大家好，欢迎来到IT知识分享网。

以下是C语言实现正则表达式的代码：

#include <stdbool.h> #include <string.h> #include <stdlib.h> bool isMatch(char* s, char* p) { int m = strlen(s); int n = strlen(p); // 检查模式p的合法性，避免无效的'*' for (int i = 0; i < n; ++i) { if (p[i] == '*' && (i == 0 || p[i-1] == '*')) { return false; } } // 创建动态规划表，dp[i][j]表示s的前i个字符和p的前j个字符是否匹配 bool *dp = (bool *)calloc((m+1) * (n+1), sizeof(bool)); if (!dp) { return false; // 内存分配失败，但题目通常保证不会出现 } // 初始化基础情况：空字符串匹配空模式 dp[0] = true; // 初始化第一行，处理模式p可以匹配空字符串的情况（如"a*"） for (int j = 1; j <= n; ++j) { if (p[j-1] == '*') { dp[j] = dp[j-2]; // 匹配0次的情况 } } // 填充dp表 for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (p[j-1] == '*') { // 处理'*'的情况，考虑匹配0次或多次 bool matchZero = dp[i*(n+1) + (j-2)]; bool matchMore = (p[j-2] == '.' || s[i-1] == p[j-2]) && dp[(i-1)*(n+1) + j]; dp[i*(n+1)+j] = matchZero || matchMore; } else { // 处理普通字符或'.'的情况 bool currentMatch = (p[j-1] == '.' || s[i-1] == p[j-1]); dp[i*(n+1)+j] = currentMatch && dp[(i-1)*(n+1) + (j-1)]; } } } bool result = dp[m*(n+1) + n]; free(dp); return result; } void test(const char *s, const char *p, bool expected) { bool result = isMatch((char*)s, (char*)p); printf("s=\"%s\", p=\"%s\" -> %s (Expected %s)\n", s, p, result ? "true" : "false", expected ? "true" : "false"); } int main() { // 完全匹配 test("aa", "aa", true); // '.' 匹配任意字符 test("ab", "a.", true); // '*' 匹配零次 test("a", "ab*", true); // b* 匹配零次 // '*' 匹配多次 test("aaa", "a*", true); // a* 匹配三次 test("ab", "a*b", true); // a* 匹配一次 // 复杂组合 test("aab", "c*a*b", true); // c* 匹配零次，a* 匹配两次 test("mississippi", "mis*is*p*.", false); // 无法匹配 // 无效模式 test("a", "a", false); // 连续 '*' 非法 // 空字符串 test("", "", true); // 空字符串匹配空模式 test("", "a*", true); // a* 匹配零次 // 边界情况 test("a", ".*", true); // .* 匹配任意字符 return 0; }

代码解析

1. 合法性检查
   确保模式 p 中的 * 不连续且不位于开头。例如 a 或 *a 是非法的。
2. 动态规划表初始化

• 使用 calloc 分配 (m+1)*(n+1) 的布尔数组，初始值为 false。
• dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配。

3. 基础情况

• dp[0][0] = true：空字符串与空模式匹配。
• 第一行处理模式 p 匹配空字符串的情况（例如 a* 可以匹配空）。

4. 填充表格

当 p[j-1] 是 * 时：

• matchZero：匹配零次（跳过 p[j-2]），即 dp[i][j-2]。
• matchMore：匹配多次（需 p[j-2] 与 s[i-1] 匹配），即 dp[i-1][j]。

5. 普通字符或 .：直接检查当前字符是否匹配，并依赖 dp[i-1][j-1]。
6. 结果提取与内存释放
   最终结果存储在 dp[m][n] 中，释放动态规划表内存。

算法复杂度

• 时间复杂度：O(m*n)，需填充 m*n 的表格。
• 空间复杂度：O(m*n)，使用一维数组模拟二维表。