首页 > 代码库 > NFA的实现
NFA的实现
此次发表的是一个不确定的自动机(NFA),它可以根据输入的正规式输出由函数映像表示的结果。
此版本可以输入括号’(‘,‘)’,但是,实现的过程理解起来有点吃力,所以,在时间允许的情况下,我还将写新文章,使用单纯递归方法实现该程序。
#include"stdio.h" #include"stdlib.h" #define MAX 200 struct Stack { int Stack[MAX]; int top; }St; struct Queue { int front; int rear; int elem[MAX]; }Q; void Input(char String[]); void initStack(); //初始化栈 void PushStack(int x); //进栈 int PopStack(); //出栈 void initQueue(); void InserQ(int x); int Gethead(); void decompose(char String[]); int deal_1(char String[],int front,int rear);//处理a.b.a... int deal_2(char String[],int front,int rear);//处理a|b|a.... int deal_3(char String[],int front,int rear);//处理a* void cut_string(int start, int end, char String[], char temp[]); int num = 0; main() { char String[MAX]; int i; while(1){initStack(); Input(String); //printf("%s",String); decompose(String);} } void Input(char String[]) { char temp; int i = 0; printf("请输入正规式:"); do{ temp = getchar(); //printf("%c",temp); String[i] = temp; i++; }while(temp != ‘\n‘); } void initStack() { St.top = -1; } void PushStack(int x) { St.top++; St.Stack[St.top] = x; } int PopStack() { int temp; temp = St.Stack[St.top]; St.top--; return temp; } void initQueue() { Q.front = Q.rear = 0; } void InserQ(int x) { if((Q.rear + 1)%MAX == Q.front) return; else { Q.elem[Q.rear] = x; Q.rear = (Q.rear + 1) % MAX; } } int Gethead() { int x; if(Q.rear == Q.front) printf("null\n"); else { x = Q.elem[Q.front]; Q.front = (Q.front+1)%MAX; } return x; } void decompose(char String[]) { int flag_index = 0; char x[MAX]; int temp; int i; while(String[flag_index] != ‘\n‘) { if(String[flag_index] == ‘(‘) { PushStack(flag_index+1); flag_index++; while(String[flag_index] != ‘\n‘ && St.top != -1) { if(String[flag_index] == ‘(‘) { PushStack(flag_index+1); flag_index++; } else if(String[flag_index] == ‘)‘) { temp = PopStack(); flag_index++; if(String[flag_index] == ‘*‘) { cut_string(temp-1,flag_index,String,x); deal_3(x,num,num); flag_index++; } else { cut_string(temp,flag_index-2,String,x); decompose(x); } } else flag_index++; } } for(i = flag_index ; String[i] != ‘\n‘ && String[i] != ‘(‘; i++); if(i != flag_index) { // printf("1"); cut_string(flag_index,i-1,String,x); num++; deal_2(x,num-1, num); } //printf("%s",cut_string(flag_index,i - 1,String)); flag_index = i; } } int deal_1(char String[],int front,int rear) { int flag_index = 0; //printf("%s",String); if(String[flag_index+1] != ‘\n‘) { printf("f(%d, %c) = %d\n",front,String[flag_index],num); flag_index++; while(String[flag_index+2] != ‘\n‘) { //printf("%c",String[flag_index]); if(String[flag_index]>=‘a‘ && String[flag_index]<=‘z‘) { printf("f(%d, %c) = %d\n",num,String[flag_index],num+1); flag_index++; num++; } else flag_index++; } // printf("%c",String[6]); printf("f(%d, %c) = %d\n",num,String[flag_index+1],rear); } else printf("f(%d, %c) = %d\n",front,String[flag_index],rear); } int deal_2(char String[],int front,int rear) { int flag_index = 0; int i = 0; int count = 0; char x[MAX]; int temp; while(String[i] != ‘\n‘) { //printf("%c",String[flag_index]); if(String[i] == ‘|‘) InserQ(i++); else i++; } if(Q.rear == Q.front) { for(i = 0; String[i] != ‘\n‘; i++) { if(String[i]>=‘a‘ && String[i]<=‘z‘) count++; } deal_1(String,front,num + count - 1); } else { while(Q.rear != Q.front) { temp = Gethead(); cut_string(flag_index,temp-1, String,x); // printf("%d",temp); num++; deal_1(x, front, rear); flag_index = temp+1; } cut_string(flag_index,i, String,x); deal_1(x, front, rear); } } int deal_3(char String[],int front,int rear) { int flag_index = 0; int temp; printf("f(%d, ~) = %d\n",front,++num); temp = num; if(String[flag_index+2]==‘)‘) { printf("f(%d, %c) = %d\n",temp,String[1],temp); } else { for(flag_index = 0; String[flag_index] != ‘*‘; flag_index++); String[flag_index] = ‘\n‘; decompose(String); } printf("f(%d, ~) = %d\n",temp,rear); return front; } void cut_string(int start, int end, char String[], char temp[]) { int i; end -= start; for(i = 0 ; i <= end ; i++) { temp[i] = String[start]; start++; // printf("%c",temp[i]); } temp[i] = ‘\n‘; //printf("%d ",i); // printf("%c",temp[i]); }
因为时间的关系,所以代码的注释也就没有太在意,望见谅。
NFA的实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。