Friday, September 18, 2015

a simple regular expression implementation

Implement a simple regular expression based string match. 

. - any character
* - match 0 or more times of previous character

/**
     *
     * @param target
     * @param regex
     * @return
     */
    public static boolean isMatch(String target, String regex){
        assert !target.isEmpty() && !regex.isEmpty();
        int p1 = 0;
        int p2 = 0;
        int len1 = target.length();
        int len2 = regex.length();
        char pre = '\0', c1, c2 = '\0';
       
        while(p1<len1 && p2<len2){
            c1 = target.charAt(p1);
            c2 = regex.charAt(p2);
           
            if(c2 == '.'){
                p1++;p2++;
                pre = '.';
            }else if(c2 == '*'){               
                if(pre == '\0'){
                    return false;
                }
                else if(pre == '.' || pre == c1){
                    p1++;
                }else{
                    p2++;
                    pre = '\0';
                }
            }else{
                if(c1 == c2){
                    pre = c1;
                    p1++; p2++;
                }else{
                    if(p2+1<len2 && regex.charAt(p2+1) == '*'){
                        p2++;p2++;
                    }else
                        return false;
                }
                   
            }
        }
       
        if(p1 == len1)
            return true;
        else
            return false;
    }

2 comments:

  1. I tested several case. It doesn't pass ("abcde", "?b?*e"), ("abcde", "?b?d?"). This is my try: http://allenlipeng47.com/PersonalPage/index/view/195/nkey

    ReplyDelete
    Replies
    1. no ?, this question doesn't contain ? only . and *

      Delete