Wie schreibe ich eine einfache Funktion zum Abgleich regulärer Ausdrücke in C oder C++?

Question

Dies ist eine Frage in meiner heutigen Klausur, die Funktionssignatur lautet

int is_match(char* pattern,char* string)

Das Muster ist nur auf ASCII-Zeichen beschränkt und die Quantifizierung * y ? Es ist also relativ einfach. is_match sollte bei Übereinstimmung 1 zurückgeben, ansonsten 0.

Wie kann ich das tun?

Answer 1

Brian Kernighan hat einen kurzen Artikel über Ein Abgleich mit regulären Ausdrücken que Rob Pike als Demonstrationsprogramm für ein Buch geschrieben, an dem sie arbeiteten. Der Artikel ist sehr lesenswert und erklärt ein wenig über den Code und reguläre Ausdrücke im Allgemeinen.

Ich habe mit diesem Code gespielt und einige Änderungen vorgenommen, um mit einigen Erweiterungen zu experimentieren, wie z. B. die Rückgabe der Stelle in der Zeichenkette, an der das Muster übereinstimmt, so dass die Teilzeichenkette, die dem Muster entspricht, aus dem Originaltext kopiert werden kann.

Aus dem Artikel:

Ich habe Rob vorgeschlagen, dass wir die Ausdruckspaket zu finden, das die grundlegenden Ideen veranschaulicht und gleichzeitig eine nützliche und nicht triviale Klasse von Mustern erkennt. Idealerweise sollte der Code auf eine einzige Seite passen.

Rob verschwand in seinem Büro, ein erschien er innerhalb von ein oder zwei Stunden wieder mit den 30 Zeilen C Code, der anschließend in Kapitel 9 von TPOP erschien. [ ] implementiert einen Matcher für reguläre Ausdrücke, der diese Konstrukte verarbeitet:

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

Dies ist eine recht nützliche Klasse; nach meiner eigenen Erfahrung bei der Verwendung regulärer Ausdrücke im täglichen Gebrauch, macht sie leicht 95 Prozent aller aller Fälle. In vielen Situationen ist das Lösen des richtigen Problems ein ein großer Schritt auf dem Weg zu einem schönen Programm. Rob gebührt große Anerkennung dafür, dass er aus einer großen Anzahl von Optionen eine sehr kleine, aber wichtige aber dennoch wichtigen, gut definierten und erweiterbaren Satz von Funktionen.

Die Umsetzung von Rob selbst ist eine großartige kompakt, elegant, effizient und nützlich. Es ist eines der besten Beispiele der Rekursion, die ich je gesehen habe, und es zeigt die Leistungsfähigkeit von C Zeigern. Obwohl wir damals vor allem daran interessiert waren, zu vermitteln die wichtige Rolle einer guten Notation für die Benutzerfreundlichkeit eines Programms und vielleicht auch einfacher zu schreiben ist, ist der Code für reguläre Ausdrücke auch eine hervorragende Möglichkeit, Algorithmen, Datenstrukturen Strukturen, Testen, Leistungssteigerung und andere wichtige Themen.

Der eigentliche C-Quellcode aus dem Artikel ist sehr, sehr schön.

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

Siehe Diese Frage für eine Lösung, die Sie nicht vorlegen können. Siehe dieses Papier für eine Beschreibung, wie man eine besser lesbare Version implementieren kann.

Answer 3

Hier ist eine rekursiv erweiterbare Implementierung. Getestet für die erste Ordnung der Musterkomplexität.

#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;
}

Wenn etwas unklar ist, fragen Sie nach.

Answer 4

Versuchen Sie, eine Liste interessanter Testfälle zu erstellen:

is_match("Dummy", "Dummy") sollte true zurückgeben;

is_match("dumm?y", "dumm") sollte true zurückgeben;

is_match("dum?y", "dummy") sollte false zurückgeben;

is_match("dum*y", "dummy") sollte true zurückgeben;

und so weiter ...

dann sehen, wie man den leichteren Test bestehen kann, dann den nächsten ...

Answer 5

Schummeln. Verwenden Sie #include <boost/regex/regex.hpp> .