如何在C或C++中编写简单的正则表达式模式匹配函数？

Question

这是我今天的论文测试中的一个问题,函数签名是

int is_match(char* pattern,char* string)

图案仅限于ASCII字符和量化*和?,所以它是比较简单的.is_match如果匹配则返回1,否则返回0.

我该怎么做呢？

Answer 1

Brian Kernighan提供了一篇关于A正则表达式匹配器的简短文章,Rob Pike将其作为他们正在撰写的一本书的演示程序.这篇文章是一篇非常好的读物,解释了一般的代码和正则表达式.

我已经使用了这段代码,进行了一些更改以尝试一些扩展,例如还返回模式匹配的字符串中的位置,以便可以从原始文本复制匹配模式的子字符串.

来自文章:

我向Rob建议我们需要找到最小的正则表达式包来说明基本的想法,同时仍然认识到一个有用的和非平凡的模式类.理想情况下,代码适合单个页面.

Rob消失在他的办公室里,至少在我现在记得的时候,在不超过一两个小时的时间内出现了30行C代码,随后出现在TPOP的第9章中.该代码实现了一个处理这些结构的正则表达式匹配器:

c    matches any literal character c
.    matches any single character
^    matches the beginning of the input string
$    matches the end of the input string
*    matches zero or more occurrences of the previous character

这是一个非常有用的课程; 根据我自己在日常使用正则表达式的经验,它很容易占所有实例的95%.在许多情况下,解决正确的问题是迈向美好计划的重要一步.Rob选择如此明智,从众多选项中选择一个非常小但重要,定义明确且可扩展的功能集,值得称赞.

Rob的实现本身就是美丽代码的极好例子:紧凑,优雅,高效和实用.这是我见过的最好的递归示例之一,它展示了C指针的强大功能.虽然当时我们最感兴趣的是传达一个好的符号在使程序更易于使用和可能更容易编写方面的重要作用,但正则表达式代码也是说明算法,数据结构,测试的绝佳方法,性能增强和其他重要主题.

文章中的实际C源代码非常好.

/* 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;
}

Answer 2

有关您无法提交的解决方案,请参阅此问题.有关如何实现更具可读性的说明,请参阅此文章.

Answer 3

这是递归可扩展实现。测试了模式复杂性的一阶。

#include <string.h>
#include <string>
#include <vector>
#include <iostream>

struct Match {
  Match():_next(0) {}
  virtual bool match(const char * pattern, const char * input) const {
    return !std::strcmp(pattern, input);
  }
  bool next(const char * pattern, const char * input) const {
    if (!_next) return false;
    return _next->match(pattern, input);
  }
  const Match * _next;
};

class MatchSet: public Match {
  typedef std::vector<Match *> Set;
  Set toTry;
public:
  virtual bool match(const char * pattern, const char * input) const {
    for (Set::const_iterator i = toTry.begin(); i !=toTry.end(); ++i) {
      if ((*i)->match(pattern, input)) return true;
    }
    return false;
  }
  void add(Match * m) {
    toTry.push_back(m);
    m->_next = this;
  }
  ~MatchSet() {
    for (Set::const_iterator i = toTry.begin(); i !=toTry.end(); ++i)
      if ((*i)->_next==this) (*i)->_next = 0;
  }
};

struct MatchQuestion: public Match  {
  virtual bool match(const char * pattern, const char * input) const {
    if (pattern[0] != '?')
      return false;
    if (next(pattern+1, input))
      return true;
    if (next(pattern+1, input+1))
      return true;
    return false;
  }
};

struct MatchEmpty: public Match {
  virtual bool match(const char * pattern, const char * input) const {
    if (pattern[0]==0 && input[0]==0)
      return true;
    return false;
  }
};

struct MatchAsterisk: public Match {
  virtual bool match(const char * pattern, const char * input) const {
    if (pattern[0] != '*')
      return false;
    if (pattern[1] == 0) {
      return true;
    }
    for (int i = 0; input[i] != 0; ++i) {
      if (next(pattern+1, input+i))
        return true;
    }
    return false;
  }
};

struct MatchSymbol: public Match {
  virtual bool match(const char * pattern, const char * input) const {
    // TODO: consider cycle here to prevent unnecessary recursion
    // Cycle should detect special characters and call next on them
    // Current implementation abstracts from that
    if (pattern[0] != input[0])
      return false;
    return next(pattern+1, input+1);
  }
};

class DefaultMatch: public MatchSet {
  MatchEmpty empty;
  MatchQuestion question;
  MatchAsterisk asterisk;
  MatchSymbol symbol;
public:
  DefaultMatch() {
    add(&empty);
    add(&question);
    add(&asterisk);
    add(&symbol);
  }
  void test(const char * p, const char * input) const {
    testOneWay(p, input);
    if (!std::strcmp(p, input)) return;
    testOneWay(input, p);
  }
  bool testOneWay(const char * p, const char * input) const {
    const char * eqStr = " == ";
    bool rv = match(p, input);
    if (!rv) eqStr = " != ";
    std::cout << p << eqStr << input << std::endl;
    return rv;
  }

};


int _tmain(int argc, _TCHAR* argv[])
{
  using namespace std;

  typedef vector<string> Strings;
  Strings patterns;

  patterns.push_back("*");
  patterns.push_back("*hw");
  patterns.push_back("h*w");
  patterns.push_back("hw*");

  patterns.push_back("?");
  patterns.push_back("?ab");
  patterns.push_back("a?b");
  patterns.push_back("ab?");

  patterns.push_back("c");
  patterns.push_back("cab");
  patterns.push_back("acb");
  patterns.push_back("abc");

  patterns.push_back("*this homework?");
  patterns.push_back("Is this homework?");
  patterns.push_back("This is homework!");
  patterns.push_back("How is this homework?");

  patterns.push_back("hw");
  patterns.push_back("homework");
  patterns.push_back("howork");

  DefaultMatch d;
  for (unsigned i = 0; i < patterns.size(); ++i)
    for (unsigned j =i; j < patterns.size(); ++j)
      d.test(patterns[i].c_str(), patterns[j].c_str());

    return 0;
}

如果有不清楚的地方，请询问。

Answer 4

尝试列出一些有趣的测试用例：

is_match("dummy","dummy") 应该返回 true；

is_match("dumm?y","dummy") 应该返回 true；

is_match("dum?y","dummy") 应该返回 false；

is_match("dum*y","dummy") 应该返回 true；

等等 ...

然后看看如何让更容易的测试通过，然后下一个......