Wildcard matching strings

Question

I am trying to write a function bool match(char pattern[], char expresssion[]) which checks if the pattern matches the expression. If * appears in the pattern, it can be matched with any string - the empty string as well. This is where my problem arises.

I am trying to cater for this star. My first idea was to check the next character that appears after the star and see whether it appears in the expression. If it appears at the n-th position, I move one-character in the pattern and start checking the expression further from the n-th position. However, it is not always obvious whether I should check my expression from the left or from the right. For example - if checked from the left, then this test would fail:

match("a*b", "ababab")

because only the first "b" would be "devoured" by the star. On the contrary, if I checked from the right, then this test would fail:

match("a*b*b*", "abbbbbbbba")

Could you give me a hint how I could deal with this star?

Why downvote? Could you explain to me what is wrong with my question so that I can improve in the future? — Aemilius, Jan 29 '18 at 10:09
Not my downvote, but probably because the question s somewhat too broad. — Jabberwocky, Jan 29 '18 at 10:16
https://stackoverflow.com/questions/30299671/matching-strings-with-wildcard/30300521#30300521 — Dmitry Bychenko, Jan 29 '18 at 11:39

score 3 · Accepted Answer · answered Jan 29 '18 at 09:44

The trick is to write a recursive function and match chars like for like until you find a '*'. Once '*' has been encountered then anything is fair game, so you can return true.

bool match(char const *pattern, char const *file) {
    for (; *pattern != '\0'; ++pattern) {
        switch (*pattern) {
        case '*': {
            //if pattern terminates after * then file can be anything, thus
            //terminate and return true.
            if (pattern[1] == '\0')
                return true;
            //pattern doesn't terminate so cut off '*' from pattern,
            //increment file and repeat.
            size_t max = strlen(file);
            for (size_t i = 0; i < max; i++)
                if (match(pattern + 1, file + i))
                    return true;
            return false;
        }
        default:
            //if pattern doesn't specify a '?' or a '*', it must be a regular
            //character and so, must require a like for like match with file.
            if (*file != *pattern)
                return false;
            ++file;
        }
    }
    //we have iterated through the whole of pattern and so file must end too
    //if we are to match.
    return *file == '\0';
}

You can then add extra branches to the switch statement and add functionality to your glob tool. For example, try adding the logic for a '?'.

Wildcard matching strings

1 Answers1