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

Ich habe das nicht getestet, nicht programmiert und nicht debuggt, aber vielleicht ist das ein Anfang...

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 2

Die volle Leistungsfähigkeit regulärer Ausdrücke und endlicher Zustandsautomaten ist zur Lösung dieses Problems nicht erforderlich. Als Alternative gibt es eine relativ einfache Lösung durch dynamische Programmierung.

Match(i, j) sei 1, wenn es möglich ist, die Teilzeichenkette String [i..n-1] mit dem Teil-Muster Muster [j, m - 1], wobei n und m die Längen der String y Muster beziehungsweise. Andernfalls sei match(i, j) gleich 0.

Die Basisfälle sind:

• match(n, m) = 1, können Sie eine leere Zeichenkette mit einem leeren Muster vergleichen;

• match(i, m) = 0, kann man eine nicht leere Zeichenfolge nicht mit einem leeren Muster vergleichen;

Der Übergang ist in drei Fälle unterteilt, je nachdem, ob das aktuelle Teilmuster mit einem Zeichen, gefolgt von einem '*', oder einem Zeichen, gefolgt von einem '?', oder einfach mit einem Zeichen ohne nachfolgendes Sonderzeichen beginnt.

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

Die Zeitkomplexität dieses Ansatzes ist O(n * m). Die Speicherkomplexität ist ebenfalls O(n * m), kann aber mit einer einfachen Änderung auf O(m) reduziert werden.

Answer 3

Einfache rekursive Implementierung. Sie ist langsam, aber leicht zu verstehen:

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

Ich hoffe, ich habe alles richtig verstanden.

Answer 4

Ein C-Programm, um den Index zu finden, ab dem die Teilzeichenkette in der Hauptzeichenkette beginnen soll. Code hier eingeben

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