Làm cách nào để viết một hàm biểu thức chính quy đơn giản phù hợp trong C hoặc C++?

Question

Đây là một câu hỏi trong bài kiểm tra giấy của tôi ngày hôm nay, chữ ký chức năng là

int is_match(char* pattern,char* string) 

Các mô hình được giới hạn ký tự ASCII chỉ và định lượng * và ?, vì vậy nó là tương đối đơn giản. is_match phải trả lại 1 nếu phù hợp, nếu không 0.

Làm cách nào để thực hiện việc này?

Answer 1

cố gắng để tạo ra một danh sách các trường hợp thử nghiệm thú vị:

is_match ("giả", "giả") nên return true;

is_match ("dumm? Y", "dummy") nên trả về true;

is_match ("dum? Y", "dummy") phải trả về false;

is_match ("dum * y", "dummy") nên trả về true;

và vân vân ...

sau đó xem làm thế nào để làm cho qua kiểm tra dễ dàng hơn, thì người tiếp theo ...

Answer 2

Cheat. Sử dụng #include <boost/regex/regex.hpp>.

Answer 3

Không kiểm tra điều này, thực sự mã hóa nó, hoặc gỡ lỗi nó, nhưng điều này có thể giúp bạn có được một sự khởi đầu ...

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 4

Xem This Question kiếm một giải pháp bạn không thể gửi. Hãy xem this paper để biết mô tả cách triển khai một cách dễ đọc hơn.

Answer 5

Toàn bộ sức mạnh của cụm từ thông dụng và máy trạng thái hữu hạn không cần thiết để giải quyết vấn đề này. Là một giải pháp thay thế có một giải pháp lập trình động tương đối đơn giản.

trận đấu Lết (i, j) là 1 nếu nó có thể phù hợp với các tiểu chuỗi chuỗi [i..n-1] với phụ mẫu mẫu [j, m - 1] , trong đó n và m là độ dài của chuỗi và mẫu tương ứng. Nếu không để cho trận đấu (i, j) là 0.

Các trường hợp cơ sở là:

• trận đấu (n, m) = 1, bạn có thể kết hợp một chuỗi rỗng với một mô hình rỗng;

• đối sánh (i, m) = 0, bạn không thể đối sánh chuỗi không trống với mẫu trống;

Chuyển đổi được chia thành 3 trường hợp tùy thuộc vào việc mẫu con hiện tại có bắt đầu bằng ký tự theo sau dấu '*' hay ký tự theo sau là '?' hoặc chỉ bắt đầu với một nhân vật không có biểu tượng đặc biệt sau đó.

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

Độ phức tạp của phương pháp này là O (n * m). Độ phức tạp của bộ nhớ cũng là O (n * m) nhưng với một sửa đổi đơn giản có thể được giảm xuống O (m).

Answer 6

Đây là triển khai có thể mở rộng đệ quy. Đã kiểm tra cho thứ tự đầu tiên của mô hình phức tạp.

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

Nếu có điều gì đó không rõ ràng, hãy hỏi.

Answer 7

Triển khai đệ quy đơn giản. Nó rất chậm nhưng dễ hiểu:

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

Hy vọng tôi hiểu rồi.

Answer 8

Brian Kernighan cung cấp một bài viết ngắn trên A Regular Expression Matcher rằng Rob Pike đã viết như một chương trình trình diễn cho một cuốn sách mà họ đang làm việc. Bài viết là một bài đọc rất hay giải thích một chút về mã và các biểu thức thông thường nói chung.

Tôi đã chơi với mã này, thực hiện một vài thay đổi để thử nghiệm với một số tiện ích mở rộng, cũng như trả lại vị trí trong chuỗi phù hợp để chuỗi con khớp với mẫu có thể được sao chép từ văn bản gốc.

Từ bài viết:

Tôi đề nghị với Rob rằng chúng tôi cần phải tìm ra thường xuyên gói biểu hiện nhỏ nhất mà sẽ minh họa cho ý tưởng cơ bản trong khi vẫn nhận một lớp học hữu ích và không tầm thường của các mô hình. Lý tưởng nhất, mã sẽ vừa với một trang.

Rob biến mất vào văn phòng của mình, và ít nhất là tôi nhớ nó ngay bây giờ, xuất hiện lại không quá một hoặc hai giờ với 30 dòng mã C sau đó xuất hiện trong Chương 9 của TPOP. Mã đó triển khai đối sánh cụm từ thông dụng xử lý các cấu trúc này:

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 

Đây là lớp học hữu ích; theo kinh nghiệm của riêng tôi về việc sử dụng các biểu thức thông thường trên cơ sở hàng ngày, nó dễ dàng chiếm 95% của tất cả các trường hợp. Trong nhiều trường hợp, giải quyết vấn đề đúng là bước lớn trên con đường đến một chương trình tuyệt đẹp. Rob xứng đáng nhận được tín dụng tuyệt vời để lựa chọn một cách khôn ngoan, từ trong số nhiều tùy chọn, một số rất nhỏ nhưng vẫn quan trọng, được xác định rõ và có thể mở rộng các tính năng.

Tự thực hiện của Rob là một ví dụ tuyệt vời về mã đẹp: nhỏ gọn, thanh lịch, hiệu quả và hữu ích. Đó là một trong những ví dụ tốt nhất của đệ quy mà tôi đã từng thấy, và nó cho thấy sức mạnh của C con trỏ. Mặc dù tại thời điểm chúng tôi quan tâm nhất đến việc chuyển tải vai trò quan trọng của một ký hiệu tốt trong việc giúp chương trình dễ sử dụng hơn và dễ viết hơn, mã biểu thức chính quy cũng là một cách tuyệt vời để minh họa thuật toán, dữ liệu cấu trúc, kiểm tra, tăng cường hiệu suất và các chủ đề quan trọng khác .

Mã nguồn C thực tế từ bài viết rất hay.

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

Chương trình C để tìm chỉ mục, từ đó chuỗi con trong chuỗi chính sẽ bắt đầu. enter code here

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

}