Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

After reading @JavaDeveloper's recent question, I was inspired1 to try my hand at writing code to accomplish the same task.

The "rules" for this code (i.e., its intent) is to match a subset of regular expressions, defined as follows:

  1. . (dot) means a any single character match
  2. * (star) means 0 or more character match
  3. ? (question) means previous char is an option i.e colou?r matches color and colour.

Just to be clear: I'm well aware that this is not how regular expressions are normally defined, and that the fundamental capability of this subset is exactly that--a subset of what full regexes can recognize/match.

As an aside: although tagging a question with both C and C++ is normally a mistake, I believe in this case it's justified. In particular, the match function is at least intended to be work as either C or C++. The test rig (enabled by defining TEST when compiling) uses features to specific to C++, but match itself should not.

Without further ado, my attempt at implementing this functionality:

#include <string.h>
#ifndef __cplusplus
#include <stdbool.h>
#endif

bool match(char const *needle, char const *haystack) {
    for (; *needle!='\0'; ++needle) {
        switch (*needle) {
        case '.': ++haystack;
        case '?': break;
        case '*': {
            size_t max = strlen(needle);
            for (size_t i = 0; i < max; i++)
                if (match(needle + 1, haystack + i))
                    return true;
            return false;
        }
        default:
            if (*haystack == *needle) 
                ++haystack;
            else if (needle[1] != '?')
                return false;
        }
    }
    return *haystack == '\0';
}

#ifdef TEST
#include <iostream>
#include <vector>
#include <string>

template<class F> 
void assertTrue(F f, char const *needle, char const *hay_stack) {
    static const std::string names [] = { "Failure", "Success" };
    std::cout << names[f(needle, hay_stack)];
    std::cout << " for: " << needle << "->" << hay_stack << "\n";
}

template<class F>
void assertFalse(F f, char const *needle, char const *hay_stack) {
    static const std::string names [] = { "Success", "Failure" };
    std::cout << names[f(needle, hay_stack)];
    std::cout << " for: " << needle << "->" << hay_stack << "\n";
}

int main(){
    assertTrue(match,"colou?**rs", "colours");
    assertTrue(match,"colou?**rs", "colors");

    assertTrue(match,"colou**?rs", "colours");
    // assertTrue(RegexToy.match,"colou**?rs", "colors"); <---- exlusive case.

    assertTrue(match,"colou?**r", "colour");
    assertTrue(match,"colou?**r", "color");

    assertTrue(match,"colou?*", "colou");
    assertTrue(match,"colou?*", "colo");

    assertTrue(match,"colou?r", "colour");
    assertTrue(match,"colou?r", "color");

    assertTrue(match,"colou?*?r", "colour");
    assertTrue(match,"colou?*?r", "color");

    // Success cases
    assertTrue(match,"", "");
    assertTrue(match, "***", "");

    std::vector<char const *> regexList { "abc****", "abc", "a*b*c", "****abc", "**a**b**c****", "abc*" };
    char const *str1 = "abc";

    for (auto regex : regexList) 
        assertTrue(match,regex, str1);

    char const *regex = "abc****";
    std::vector<char const *> strList1 { "abcxyz", "abcx", "abc" };
    for (auto str : strList1) 
        assertTrue(match,regex, str);

    regex = "***abc";
    std::vector<char const *> strList2 { "xyzabc", "xabc", "abc" };
    for (auto str : strList2) 
        assertTrue(match, regex, str);  

    assertTrue(match, "a.c", "abc");
    assertTrue(match, "a*.*c", "abc");


    assertTrue(match,"a*.b.*c", "axxbxxbxxc");

    // Fail cases.
    assertFalse(match,"abc", "abcd");
    assertFalse(match,"*a", "abcd");
    assertFalse(match,"a", "");
    assertFalse(match,".a*c", "abc");
    assertFalse(match,"a.*b", "abc");
    assertFalse(match,"..", "abc");
    assertFalse(match,"", "abc");
}
#endif

  1. Along with stealing the idea from @JavaDeveloper, I also stole his test rig, with only minor editing. I hope that's not a problem (I think my making attribution to him clear mans it falls within SE's licensing).
share|improve this question
    
This is actually a complete wildcards grammar, I think. –  AJMansfield Mar 7 at 0:47
    
@AJMansfield: It is much closer to globbing than normal regexes, but I decided to keep the same rules as the previous question. –  Jerry Coffin Mar 7 at 0:55
add comment

2 Answers 2

up vote 2 down vote accepted

The regex flavour is non-standard, as you noted. Just to be clear, ? acts as a zero-or-one-of-the-previous-character modifier, while * acts more like a shell glob.

You have an access-past-the-end-of-string error when testing for glob matches in a test such as this:

assertFalse(match, "**a", "b");

The for-loop speculatively matches max substrings of the haystack, where max is based on the length of the needle. If the matches don't succeed, you could easily walk past the end of the haystack.

Your switch block is fragile: the '.' case relies on the break of the following '?' case. That's a bit too clever and dangerous for my taste, and a warning comment would be useful.

share|improve this answer
    
Good point--I'd intended strlen(haystack), but that's not quite right either. Thanks. –  Jerry Coffin Mar 6 at 20:10
add comment

The output of your unit tests is unintuitive. For example,

Success for: ..->abc

Huh? That should not match. Oh, it turns out that it was an assertFalse(). It would have been clearer to print

[PASS] Match ..->abc returns false
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.