Как мне написать простую функцию сопоставления с образцом регулярного выражения в C или C ++?

Question

Это вопрос в моем сегодняшнем бумажном тесте, подпись функции

int is_match(char* pattern,char* string)

Шаблон ограничен только ASCII-символами и квантификацией * и ?, поэтому он относительно прост. is_match должен возвращать 1, если совпадает, иначе 0.

Как мне это сделать?

Answer 1

Брайан Керниган представил небольшую статью о Средстве регулярного выражения , которое Роб Пайк написал как демонстрационную программу для книги, над которой работал. Статья очень приятно читается, объясняет немного о коде и регулярных выражениях в целом.

Я поиграл с этим кодом, внеся несколько изменений, чтобы поэкспериментировать с некоторыми расширениями, например, чтобы вернуть, где в строке соответствует шаблон, чтобы подстрока, соответствующая шаблону, могла быть скопирована из исходного текста.

Из статьи:

Я предложил Робу, что нам нужно найти самую маленькую регулярную пакет выражений, который будет иллюстрировать основные идеи, пока еще распознавание полезного и нетривиального класса паттернов. В идеале код поместится на одной странице.

Роб исчез в своем кабинете, и, по крайней мере, насколько я помню это сейчас, появился снова не более чем через час или два с 30 строками C код, который впоследствии появился в главе 9 TPOP. Этот код реализует средство сравнения регулярных выражений, которое обрабатывает следующие конструкции:

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 процентов всех случаев. Во многих ситуациях решение правильной проблемы является большой шаг на пути к красивой программе. Роб заслуживает большого уважения для того, чтобы выбирать так мудро, из широкого набора вариантов, очень маленький но важный, четко определенный и расширяемый набор функций.

Сама реализация Роба - превосходный пример красивого кода: компактный, элегантный, эффективный и полезный. Это один из лучших примеров рекурсии, которую я когда-либо видел, и это показывает силу 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

Чит.Используйте #include <boost/regex/regex.hpp>.

Answer 5

попробуйте составить список интересных тестовых случаев:

is_match ("dummy", "dummy") должно возвращать true;

is_match ("dumm? Y","пустышка") должна возвращать true;

is_match ("dum? Y", "dummy") должно возвращать false;

is_match ("dum * y", "dummy") должно возвращать true;

и так далее ...

затем посмотрите, как сделать более простой тестовый проход, чем следующий ...

Answer 6

Полная мощность регулярных выражений и конечных автоматов не требуется для решения этой проблемы.В качестве альтернативы существует относительно простое решение для динамического программирования.

Пусть match (i, j) будет 1, если возможно сопоставить подстроку string [i..n-1] с подшаблоном pattern [j, m - 1], где n и m - длины string и pattern соответственно.В противном случае пусть match (i, j) будет 0.

Базовые случаи:

• match (n, m) = 1, вы можете сопоставить пустую строку спустой шаблон;

• соответствует (i, m) = 0, вы не можете сопоставить непустую строку с пустым шаблоном;

Переходделится на 3 случая в зависимости от того, начинается ли текущий подшаблон с символа, за которым следует «*», или с символа, за которым следует «?»или просто начинается с символа без специального символа после него.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int is_match(char* pattern, char* string)
{
  int n = strlen(string);
  int m = strlen(pattern);

  int i, j;
  int **match;

  match = (int **) malloc((n + 1) * sizeof(int *));
  for(i = 0; i <= n; i++) {
    match[i] = (int *) malloc((m + 1) * sizeof(int));
  }

  for(i = n; i >= 0; i--) {
    for(j = m; j >= 0; j--) {
      if(i == n && j == m) {
        match[i][j] = 1;
      }
      else if(i < n && j == m) {
        match[i][j] = 0;
      }
      else {
        match[i][j] = 0;
        if(pattern[j + 1] == '*') {
          if(match[i][j + 2]) match[i][j] = 1;
          if(i < n && pattern[j] == string[i] && match[i + 1][j]) match[i][j] = 1;
        }
        else if(pattern[j + 1] == '?') {
          if(match[i][j + 2]) match[i][j] = 1;
          if(i < n && pattern[j] == string[i] && match[i + 1][j + 2]) match[i][j] = 1;
        }
        else if(i < n && pattern[j] == string[i] && match[i + 1][j + 1]) {
          match[i][j] = 1;
        }
      }
    }
  }

  int result = match[0][0];

  for(i = 0; i <= n; i++) {
    free(match[i]);
  }

  free(match);

  return result;
}

int main(void)
{
  printf("is_match(dummy, dummy)  = %d\n", is_match("dummy","dummy"));
  printf("is_match(dumm?y, dummy) = %d\n", is_match("dumm?y","dummy"));
  printf("is_match(dum?y, dummy)  = %d\n", is_match("dum?y","dummy"));
  printf("is_match(dum*y, dummy)  = %d\n", is_match("dum*y","dummy")); 

  system("pause");

  return 0;
}

Временная сложность этого подхода составляет O (n * m).Сложность памяти также O (n * m), но с простой модификацией может быть уменьшена до O (m).

Answer 7

Не проверял, не кодировал и не отлаживал, но это может дать вам начало ...

for each character in the pattern
  if pattern character after the current one is *
    // enter * state
    while current character from target == current pattern char, and not at end
      get next character from target
    skip a char from the pattern
  else if pattern character after the current one is ?
    // enter ? state
    if current character from target == current pattern char
      get next char from target
    skip a char from the pattern
  else
    // enter character state
    if current character from target == current pattern character
      get next character from target
    else
      return false
return true

Answer 8

AC программа для поиска индекса, с которого начинается подстрока в главной строке.введите код здесь

#include<stdio.h>
int mystrstr (const char *,const char *);
int mystrcmp(char *,char *);
int main()
{
    char *s1,*s2;//enter the strings, s1 is main string and s2 is substring.
    printf("Index is %d\n",mystrstr(s1,s2));
    //print the index of the string if string is found
}
//search for the sub-string in the main string
int mystrstr (const char *ps1,const char *ps2) 
{
    int i=0,j=0,c=0,l,m;char *x,*y;
    x=ps1;
    y=ps2;
    while(*ps1++)i++;
    while(*ps2++)j++;
    ps1=x;
    ps2=y;
    char z[j];
    for(l=0;l<i-j;l++)
    {
        for(m=l;m<j+l;m++)
            //store the sub-string of similar size from main string
            z[c++]=ps1[m];
        z[c]='\0'
        c=0;
        if(mystrcmp(z,ps2)==0)
        break;
    }
    return l;
}


int mystrcmp(char *ps3,char *ps4) //compare two strings
{
    int i=0;char *x,*y;
    x=ps3;y=ps4;
    while((*ps3!=0)&&(*ps3++==*ps4++))i++;      
    ps3=x;ps4=y;
    if(ps3[i]==ps4[i])
        return 0;
    if(ps3[i]>ps4[i])
        return +1;
    else
        return -1;
}

Answer 9

Простая рекурсивная реализация. Это медленно, но легко понять:

int is_match(char *pattern, char *string)
{
    if (!pattern[0]) {
        return !string[0];
    } else if (pattern[1] == '?') {
        return (pattern[0] == string[0] && is_match(pattern+2, string+1))
            || is_match(pattern+2, string);
    } else if (pattern[1] == '*') {
        size_t i;
        for (i=0; string[i] == pattern[0]; i++)
            if (is_match(pattern+2, string+i)) return 1;
        return 0;
    } else {
        return pattern[0] == string[0] && is_match(pattern+1, string+1);
    }
}

Надеюсь, я все понял.