Skip to content

Instantly share code, notes, and snippets.

@klb3713

klb3713/regexp.c

Created April 30, 2014 12:30
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save klb3713/dfbcf4e854441d2f20ca to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save klb3713/dfbcf4e854441d2f20ca to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. klb3713 created this gist Apr 30, 2014.
    105 changes: 105 additions & 0 deletions regexp.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,105 @@
    /*
    * =====================================================================================
    *
    * Filename: regexp.c
    *
    * Description: 参考《代码之美》写的一个实现了. * + c ^ $六种常用语法的正则匹配器
    *
    * Version: 1.0
    * Created: 2014-4-30
    * Revision: none
    * Compiler: gcc
    *
    * Author: klbgyx7@gmail.com
    * 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;
    }