C编程；通过有限状态机程序识别字符模式

Question

我正在用 C 构建一个模式识别程序，它可以读取用户定义的字符串和用户定义的 4 个字符模式。然后该程序有一个函数来确定是否找到了模式以及最初在哪里找到该模式(根据输入文本索引)。

我知道这对你们大多数人来说都是基础知识，我只希望能快速成为一名更熟练的程序员。当我执行我的程序时，它以我无法理解的方式陷入无限循环。

我知道问题出在我的 FindMatch 函数上，而不出在输入文本和模式的读入上。我的 FindMatch 函数有什么问题？!请帮忙。

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

char *getCharBlock(int *size);
int findmatchA(char *text, char *pattern, int tsize, int psize);
void printIt(char *ptr, int index, int size);

int main(){
   char *text, *pattern; //pointers for the characters you will read
   char *p,*q,*r; //some pointer variables
   int tsize,psize,x,y,z; //some integers

   printf("Please input a sequence of character text (characters only will be stored):");
   text = getCharBlock(&tsize);

   printf(" Now input the pattern you seek to search for: ");
   pattern = getCharBlock(&psize);

   x = findmatch(text,pattern,tsize, psize);
   if(x== -1){
      printf("No Match Found \n");
      printf("No starting position for match exists \n");
   }
   else{
      printf("Match Has Been Found! \n");
      printf("Match starting position at index %d \n", x);
      printf("Remaining text after Match: \n");
      printIt(text, x+psize, tsize);
   }


   free(text);
   free(pattern);
}

char *getCharBlock(int *size){
   char *input = (char*) malloc (80*sizeof(char));
   char a;
   int i = 0;
   a = getchar();
   while(i<80 && a!= '\n'){

      if( (a>= 'a' && a <= 'z') || (a>= 'A' && a <= 'Z') ){
         *(input + i) = a;
         i++;
      }
      a = getchar();
   }
   *size = i;

   return input;
 }

 int findmatch(char *text, char *pattern, int tsize, int psize) {
   int index = 0;
   int state = 0;
   while (psize <= tsize) {

     if ((*(text + index) == *pattern) && state == 0){
         state = 1;
         index++;
          printf( "test 1 \n");
     }
     else if ((*(text + index) != *pattern) && state == 0){
          state = 0;
          index++;
          printf( "test1.1 \n");
     }
     else if (*(text + index) == *(pattern + 1) && state ==1) {
       state = 2;
       index++;
       printf( "test 2 \n");
     }
     else if (*(text + index) != *(pattern + 1) && state ==1) {
        state = 0;
        printf("test 2.2 \n");
     }
     else if (*(text + index) == *(pattern + 2) && state ==2) {
        state  = 3;
        printf("test 3 \n");
     }
     else if (*(text + index) != *(pattern + 2) && state ==2) {
        state  = 0;
        printf("test 3.3 \n");
     }
     else if (*(text + index) == *(pattern + 3) && state ==3) {
        state = 4;
        printf("test 4 \n");
     }
     else if (*(text + index) != *(pattern + 3) && state ==3) {
        state = 0;
        printf("test 4.4 \n");
     }
     else {
         return -1;
     }
     index++;
   }
   return index;
   }

Answer 1

I know this is elementary to most of you, and I just hope to quickly become a more proficient programmer

祝你好运，我给你我的建议。

一些问题导致程序无法正常运行。

it gets stuck in an infinite loop in a manner I don't understand.

1) 你在这里有永远的循环:

`while (psize <= tsize) {`

psize 永远不会改变，它永远不会达到 tsize 并且循环永远不会结束。

但这不是唯一的问题。

2) text 和 pattern 的输入字符串不以 '\0' 结尾。 注意:malloc 不是 calloc。分配的内存可以包含任何内容!为谨慎起见，您应该检查内存是否已正确分配。

3) 并非所有状态都正确地推进 index 变量:

 else if (*(text + index) == *(pattern + 2) && state ==2) {
    state  = 3;             // sg! index++; is missing!
    printf("test 3 \n");
 }
 else if (*(text + index) != *(pattern + 2) && state ==2) {
    state  = 0;
    printf("test 3.3 \n");
 }

这会妨碍正确的模式匹配。

4) 未进行输入验证，例如:您应该确保 pattern 恰好是 4 个字符长。

如果我只能给你一个建议，那就是:“永远不要使用 if-else 链!”。将其替换为 switch-case-break 结构。

您的 int findmatch 就是一个完美的例子。 if-else 链创建了难以调试的丛林。你们的状态非常相似，应该创造和谐。他们不是。您的功能可以替换为更简单的功能:

int findmatch(char *text, char *pattern, int tsize, int psize) { 
   int index = 0;
   int state = 0;       
   printf("Text=<%s> pattern=<%s> tsize=%d psize=%d \n",text, pattern, tsize, psize);
   while (index <= tsize) {

       switch (state)
       {
           case 0:
                state = next_state(text,pattern, "test 1", "test1.1", &index, 0, 1, 1);
            break;                
            case 1:  // pattern[0]          matched
                state = next_state(text, pattern, "test 2", "test2.2", &index, 1, 2, 0);
            break;
            case 2:  // pattern [0] [1]     matched
                state = next_state(text, pattern, "test 3", "test3.3", &index, 2, 3, 0);
            break;                
            case 3:  // pattern [0] [1] [2] matched
                state = next_state(text, pattern, "test 4", "test4.4", &index, 3, 4, 0);
            break;                
            case 4:
                printf("DONE, index = %d \n",index);
                return index;
            break;                
            default:
                printf("We should not be here! \n");
            break;
       } // case
   } // while       
   return -1;
}

编程就像创作音乐或绘画。你的创作应该是美丽的。保持和谐，保持平衡。

这是您学习的工作计划。

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

char *getCharBlock(int *size);
int findmatch(char *text, char *pattern, int tsize, int psize);
void printIt(char *ptr, int index, int size);

void printIt(char *ptr, int index, int size)
{
}

int main(void){
   char *text, *pattern;    // pointers for the characters you will read
   int tsize,psize,x;       // some integers

   printf("Please input a sequence of character text (characters only will be stored):\n");

   text = getCharBlock(&tsize);

   printf("Now input the pattern you seek to search for: \n");
   pattern = getCharBlock(&psize);

   x = findmatch(text, pattern, tsize, psize);

   if(x == -1){
      printf("No Match Found \n");
      printf("No starting position for match exists \n");
   }
   else{
      printf("Match Has Been Found! \n");
      printf("Match starting position at index %d \n", x - 4);
      printf("Remaining text after Match: <%s> \n", text + x );

      printIt(text, x+psize, tsize);
   }

   free(text);
   free(pattern);
}

char *getCharBlock(int *size){

   char *input = (char*) malloc (80*sizeof(char) +1 );
   if (input == NULL)
   {
       printf("No memory!\n");
       exit(-1);
   }

   char a;
   int i = 0;

   a = getchar();

   while( i<80 &&  a != '\n'){

      if( ((a>= 'a') && (a <= 'z'))  || ( (a>= 'A') &&  (a <= 'Z') ) ){

         * (input + i) = a;

         i++;
      }

      a = getchar();
   }

    * (input + i)  = 0; // sg7! terminate the string 

   *size = i;

   return input;
 }

int next_state(char *text, char *pattern, char *m1, char *m2, int *index, int patternInd, int next_state, int advInd )
{
    int state = 0;

    if (text[*index] == pattern[patternInd]){
        state = next_state;
        printf( "%s\n", m1);
        (*index)++;
    }
    else{
        printf( "%s\n", m2);
        if(advInd)
            (*index)++; 
    }
    return state;       
}

int findmatch(char *text, char *pattern, int tsize, int psize) {

   int index = 0;
   int state = 0;

   printf("Text=<%s> pattern=<%s> tsize=%d psize=%d \n",text, pattern, tsize, psize);
   while (index <= tsize) {

       switch (state)
       {
           case 0:
                state = next_state(text,pattern, "test 1", "test1.1", &index, 0, 1, 1);
            break;

            case 1:  // pattern[0]          matched
                state = next_state(text, pattern, "test 2", "test2.2", &index, 1, 2, 0);
            break;

            case 2:  // pattern [0] [1]     matched
                state = next_state(text, pattern, "test 3", "test3.3", &index, 2, 3, 0);
            break;

            case 3:  // pattern [0] [1] [2] matched
                state = next_state(text, pattern, "test 4", "test4.4", &index, 3, 4, 0);
            break;

            case 4:
                printf("DONE, index = %d \n",index);
                return index;
            break;

            default:
                printf("We should not be here! \n");
            break;
       } // case
   } // while

   return -1;
}

输出:

Please input a sequence of character text (characters only will be stored):                                                                   
aaabcdef                                                                                                                                      
Now input the pattern you seek to search for:                                                                                                
abcd                                                                                                                                          
Text=<aaabcdef> pattern=<abcd> tsize=8 psize=4                                                                                                
test 1                                                                                                                                        
test2.2                                                                                                                                       
test 1                                                                                                                                        
test2.2                                                                                                                                       
test 1                                                                                                                                        
test 2                                                                                                                                        
test 3                                                                                                                                        
test 4                                                                                                                                        
DONE, index = 6                                                                                                                               
Match Has Been Found!                                                                                                                         
Match starting position at index 2                                                                                                            
Remaining text after Match: <ef>                                                                                                              


Please input a sequence of character text (characters only will be stored):                                                                   
abcdefgh                                                                                                                                      
Now input the pattern you seek to search for:                                                                                                 
efgh                                                                                                                                          
Text=<abcdefgh> pattern=<efgh> tsize=8 psize=4                                                                                                
test1.1                                                                                                                                       
test1.1                                                                                                                                       
test1.1                                                                                                                                       
test1.1                                                                                                                                       
test 1                                                                                                                                        
test 2                                                                                                                                        
test 3                                                                                                                                        
test 4                                                                                                                                        
DONE, index = 8                                                                                                                               
Match Has Been Found!                                                                                                                         
Match starting position at index 4                                                                                                            
Remaining text after Match: <>  

希望对你有所帮助。如果您有更多问题，请随时提问。