2

The title is pretty explicit and below are couple of samples input/output. Note that the regexps used are supposed to match from beginning to end of the string.

'abc' =~ 'abc' (match)
'abc' =~ 'a*bc' (match)
'aaaaaaabc' =~ 'c*bc' (no match)
'aaaaaaabc' =~ 'a.*bc' (match)
'abbbbaaaaaabc' =~ 'ab*a*b*c' (match)
'abbbbaaaaaabc' =~ 'ab*a*h*bc' (match)
'bbd' =~ 'b*bbd' (match)
'bbd' =~ '.*bbd' (match)
'bbd' =~ '.*cbd' (no match)
'' =~ '.*' (match)

My implementation for this is located at:

https://github.com/jpbillaud/piexposed/blob/master/string/string_match_regexp.c

Now I was wondering if anybody would think about a more interesting way to solve this using DP, Finite Automata or whatever else.

7
  • Is ko supposed to mean it doesn't match? Are all your regexps implicitly anchored to the beginning and end of the string? Feb 19, 2012 at 0:08
  • Your code has some bugs. Doesn't handle "bb", '.' only matches the current character, when each character could be matched, nor would it handle backtracking if necessary. Feb 19, 2012 at 0:10
  • @KeithThompson that's right "ko" means does not match and the regexps are implicitly anchored to the beginning and end of the string. Feb 19, 2012 at 0:25
  • 2
    This might do better on codereview
    – Dave
    Feb 19, 2012 at 0:46
  • 1
    @Jean-PascalBillaud: You should update the question to make those assumptions explicit. Feb 19, 2012 at 1:18

2 Answers 2

8

Take a look at this implementation of a regular expression matcher by Rob Pike, taken from the book The Practice of Programming. It's absolutely beautiful code, in just 35 lines of C it happens to meet all the requirements in the question (and a bit more!). Quoting from the article referenced above:

/* match: search for regexp anywhere in text */
int match(char *regexp, char *text)
{
    if (regexp[0] == '^')
        return matchhere(regexp+1, text);
    do {    /* must look even if string is empty */
        if (matchhere(regexp, text))
            return 1;
    } while (*text++ != '\0');
    return 0;
}

/* matchhere: search for regexp at beginning of text */
int matchhere(char *regexp, char *text)
{
    if (regexp[0] == '\0')
        return 1;
    if (regexp[1] == '*')
        return matchstar(regexp[0], regexp+2, text);
    if (regexp[0] == '$' && regexp[1] == '\0')
        return *text == '\0';
    if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
        return matchhere(regexp+1, text+1);
    return 0;
}

/* matchstar: search for c*regexp at beginning of text */
int matchstar(int c, char *regexp, char *text)
{
    do {    /* a * matches zero or more instances */
        if (matchhere(regexp, text))
            return 1;
    } while (*text != '\0' && (*text++ == c || c == '.'));
    return 0;
}
1
  • Thanks Oscar, This info is really a very good kickstarter.
    – mdev
    Mar 26, 2015 at 21:24
0

I've never tried to write a regex before, so I figured I'd give it a shot. I elided some of the boring stuff. Here's my (completely untested or compiled) version:

class Regex {
 public:
  Regex(const string& pattern) {
    // Sanity check pattern:
    if ((!pattern.empty() && pattern[0] == '*') || 
        adjacent_find(pattern.begin(), pattern.end(), both_are_repeats) != pattern.end()) {
      // throw exception
    }

    for (string::const_iterator curr(pattern.begin()), end(pattern.end()); curr != end; ) {
      char current_match = *curr;
      ++curr;
      // Fold any number of the following characters that are current_match or '*' into
      // a single Node.
      int stars = 0, count = 1;
      for (; curr != end; ++curr) {
        if (*curr == current_match) {
          ++count;
        } else if (*curr == '*') {
          ++stars;
        } else {
          break;
        }
      }
      rewritten_pattern_.push_back(Node(current_match, count - stars, stars > 0));
    }
  }

  // We could do this iteratively and avoid a stack overflow, but the recursion solution is
  // a lot easier to write, so it's good enough for SO :)
  bool matches(const string& value) const {
    return matches_internal(value.begin(), value.end(), rewritten_pattern_.begin(), rewritten_pattern_.end());
  }

 private:

  static bool matches_internal(string::const_iterator value_curr,
                               string::const_iterator value_end, 
                               vector<Node>::const_iterator pattern_curr, 
                               vector<Node>::const_iterator pattern_end) {
    for (; pattern_curr != pattern_end; ++pattern_curr) {
      // For each pattern Node, we first verify that the required count of letters is there,
      // then we handle the repeats, if specified. After this section, value_curr should
      // be advanced past the required elements of the Node.
      if (distance(value_curr, value_end) < pattern_curr->count) return false;

      string::const_iterator current_pattern_count_end = value_curr;
      advance(current_pattern_count_end, pattern_curr->count);

      if (pattern_curr->value == '.') {
        value_curr = current_pattern_count_end;
      } else {
        for (; value_curr != current_pattern_count_end; ++value_curr) {
          if (*value_curr != pattern_curr->value) {
            return false;
          }
        }
      }

      // We've handled the required charaters, now handle the repeats, if any:
      if (pattern_curr->repeats) {
        if (pattern_curr->value == '.') {
          // Here's the tricky case that will have to involve some backtracking. We aren't sure
          // how much of the string the .* should consume, we have to try all potential positions
          // and only match if any position matches. Since most regex impls are greedy
          // by default, we'll start potentially matching the whole string and move our way backward.
          ++pattern_curr;
          for (string::const_iterator wildcard_match_end = value_end;
               wildcard_match_end != value_curr;
               --wildcard_match_end) {
            if (matches_internal(wildcard_match_end, value_end, pattern_curr, pattern_end)) {
              return true;
            }
          }
          return false;
        } else {
          // If this isn't a wildcard, we can just consume all of the same value.
          for (; value_curr != value_end && *value_curr == pattern_curr->value; ++value_curr) {}
        }
      }
    }

    // After all the patterns are consumed, we only match if we have consumed the value also.
    return value_curr == value_end;
  }

  static bool both_are_repeats(char i, char j) {
    return i == '*' && j == '*';
  }

  struct Node {
    // put constructor and copy constructor here
    char value;
    int count;
    bool repeats;
  }
  vector<Node> rewritten_pattern_;
};
1
  • 2
    Annnd I just realized the question said c instead of c++. Oh well. Feb 19, 2012 at 2:52

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