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

Ответ 1

См. Этот вопрос для решения, которое вы не можете отправить. См. этот документ для описания того, как реализовать более читаемый.

Ответ 2

Здесь приведена рекурсивная расширяемая реализация. Протестировано для первого порядка сложности шаблонов.

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

Если что-то неясно, спросите.

Ответ 3

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

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

Из статьи:

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

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

Сама реализация 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;
}

Ответ 4

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

Ответ 5

Не тестировал это, на самом деле его кодировал или отлаживал, но это может привести к запуску...

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

Ответ 6

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

is_match ("dummy", "dummy") должен return true;

is_match ( "dumm? y", "dummy") должен return true;

is_match ( "дум? У", "dummy") должен возвращать false;

is_match ( "dum * y", "dummy") должен return true;

и т.д.

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

Ответ 7

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

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

Основными случаями являются:

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

• match (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).

Ответ 8

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

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

Надеюсь, у меня все получилось.

Ответ 9

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

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

Ответ 10

enter code here
#include<stdio.h>
int mystrstr(char *,char *);
int main()
{
    char *s1="123bc123abcabcd1234wx",*s2="456";
    int c =mystrstr(s1,s2);
    if(c==-1)
            printf("String is not found in the main string\n");
    else
            printf("String starts from index: %d\n",c);
 }
 int mystrstr(char *ps1,char *ps2)
 {
    static int i=0,j=0;
    if(ps1[i]==ps2[j]&&ps2[j]!='\0')
    {
            i++;j++;
            return mystrstr(ps1,ps2);
    }
    else if(j!=0)
    {
            if(ps2[j]=='\0')
                    return i-j;
            else 
            {
                    j=0;
                    return mystrstr(ps1,ps2);
            }
    }
    else if(ps1[i]=='\0')
            return -1;

    else
    {
            i++;
            return mystrstr(ps1,ps2);
    }

}