match a string using `*' operator i.e: *abc, a*bc

start_match.cpp

// test.cpp : 定义控制台应用程序的入口点。
//

#include <stdio.h>
#include <vector>
#include <string>
#include <assert.h>

struct OpCode {
    /* 0: indicate `*' operator, 1: string match */
    int op;
    std::string tomatch;
};
typedef std::vector<OpCode> OpCodes;

#define SKIPTO(p, c, op, exprs) for (; (*p op c) && *p != 0; ++p) exprs;

OpCodes parse(const char *pattern) {
    OpCodes codes;
    for ( ; *pattern; ) {
        if (*pattern == '*') {
            SKIPTO(pattern, '*', ==, ;);
            OpCode code; 
            code.op = 0;
            codes.push_back(code);
        } else {
            OpCode code;
            code.op = 1;
            SKIPTO(pattern, '*', !=, 
                code.tomatch.push_back(*pattern));
            codes.push_back(code);
        }
    }
    return codes;
}

// try match the op after a `*' op
size_t match_next_c(OpCodes::const_iterator it, OpCodes::const_iterator end, const char *str) {
    assert(it != end);
    if (++it == end) return 0;
    assert(it->op != 0 && it->tomatch.length() > 0); 
    for (size_t i = 0; i < it->tomatch.length(); ++i, ++str) 
        if (*str != it->tomatch[i]) return 0;
    return it->tomatch.length();
}

bool match(const char *str, const OpCodes &codes) {
    for (OpCodes::const_iterator it = codes.begin(); it != codes.end(); ++it) {
        const OpCode &c = *it;
        if (c.op == 0) {
            size_t matched = 0;
            while (*str && matched == 0) {
                matched = match_next_c(it, codes.end(), str);
                str += (matched == 0 ? 1 : matched);
            }
            if (matched > 0)
                ++it;
        } else { 
            for (size_t i = 0; i < it->tomatch.length(); ++i, ++str) {
                if (it->tomatch[i] != *str) return false;
            }
        }
    }
    return *str == 0;
}

bool match(const char *str, const char *pattern) {
    return match(str, parse(pattern));
}

int main(int argc, char* argv[]) {
    assert(match("abc", "abc"));
    assert(match("abc", "*"));
    assert(match("abc", "*bc"));
    assert(match("abc", "*bc*"));
    assert(match("abc", "*b*c"));
    assert(match("abc", "*abc*"));
    assert(match("abc", "a*"));
    assert(match("abc", "a*c"));
    assert(match("abc", "*c"));

    assert(!match("abc", "a"));
    assert(!match("abc", "b"));
    assert(!match("abc", "c"));
    assert(!match("abc", "bc"));
    assert(!match("abc", "d"));
    assert(!match("abc", "de"));
    assert(!match("abc", "b*c"));
    assert(!match("abc", "abcd"));
  return 0;
}