参考《代码之美》写的一个实现了. * + c ^ $六种常用语法的正则匹配器

regexp.c

/*
 * =====================================================================================
 *
 *       Filename:  regexp.c
 *
 *    Description: 参考《代码之美》写的一个实现了. * + c ^ $六种常用语法的正则匹配器
 *
 *        Version:  1.0
 *        Created:  2014-4-30
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  [email protected]
 *   Organization:  HITSZ-ICRC
 *
 * =====================================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int matchplus(char c, char *regexp, char *text);
int matchstar(char c, char *regexp, char *text);
int matchhere(char *regexp, char *text);
char* match(char *regexp, char *text);

int i;
char *matched;

int matchplus(char c, char *regexp, char *text){
    while(*text != '\0' && (*text == c || c == '.')) {
        matched[i++] = *text++;
        if(matchhere(regexp, text))
            return 1;
    };
    return 0;
}

int matchstar(char c, char *regexp, char *text){
    do {
        if(matchhere(regexp, text))
            return 1;
        if(*text != '\0' && (*text == c || c == '.'))
            matched[i++] = *text++;
        else
            break;
    } while(1);
    return 0;
}

int matchhere(char *regexp, char *text){
    if(regexp[0] == '\0')
        return 1;
    if(regexp[0] == '$' && regexp[1] == '\0')
        return *text == '\0';
    if(regexp[1] == '*')
        return matchstar(regexp[0], regexp+2, text);
    if(regexp[1] == '+')
        return matchplus(regexp[0], regexp+2, text);
    if(*text != '\0' && (regexp[0] == '.' || regexp[0] == *text)) {
        matched[i++] = *text;
        if(matchhere(regexp+1, text+1))
            return 1;
        else
            i--;
    }
    return 0;
}

char* match(char *regexp, char *text) {
    i = 0;
    matched = (char *)malloc(strlen(text)+1);
    int res;

    if(regexp[0] == '^') {
        res = matchhere(regexp+1, text);
    }
    else {
        do {
            res = matchhere(regexp, text);
            if(res == 1)
                break;
        }while(*text++ != '\0');
    }

    if(res == 1) {
        matched[i] = '\0';
    }
    else {
        free(matched);
        matched = NULL;
    }
    return matched;
}

int main()
{
    char regexp[] = "hello.c*i+world$";
    char text[] = "hello iworld";
    char* res = match(regexp, text);
    printf("%s\n", res==NULL? "not found":res);

    return 0;
}