c++实现的数据结构-ExpToMinDfa（编译原理（表达式转NFA到DFA到minDFA）.zip

#include <iostream> #include <typeinfo> #include <stdio.h> #include <iomanip> #include <set> #include <vector> #include <queue> #include <map> #include <string> #define Maxnum 99 using namespace std; //-------------------------------------------------ZZC start------------------------------------- //-------------------------------------------------表达式转NFA-------------------------------------- typedef struct Node{//根节点 char type; char Char; Node *lc; Node *rc; int start_S; int end_S; }*Tree_root; void default_Node(Node* N){//初始化根节点 N->lc = N->rc = NULL; } Node* default_L_Node(char c){//包装叶子节点 Node* N = new Node; default_Node(N); N->Char = c; N->type = 'l';//将根节点的类型设置为l return N; } int Bvisit_Tree(Tree_root Tree){//后序遍历这个树 if(Tree->type=='l'){ cout<<Tree->Char<<" "; return 1; } else{ Bvisit_Tree(Tree->lc); if(Tree->rc != NULL) Bvisit_Tree(Tree->rc); cout<<Tree->type<<" "; return 1; } } Node* default_R_Node(char type,Node* lchild,Node* rchild){//包装根节点 Node* N = new Node; default_Node(N); N->type = type; N->lc = lchild; N->rc = rchild; return N; } typedef struct op_Stack{//定义操作符栈 char* top; char* bottom; char St[Maxnum];//用数组作为栈 }; void Init_op_Stack(op_Stack &S){//对符号栈进行初始化 S.top = S.bottom = S.St; } void push_op(op_Stack &S,char a){//入栈 *(S.top)=a; S.top++; } char pop_op(op_Stack &S){//出战 S.top--; return *S.top; } char top_op(op_Stack &S){//返回栈顶元素 return *(S.top-1); } typedef struct yufa_Stack{//定义操作数栈 int top; int bottom; Node* St[Maxnum]; }; void Init_yufa_Stack(yufa_Stack &S){//初始化操作数栈 S.top=S.bottom=0; } void push_yufa(yufa_Stack &S,Node* c){//入栈 S.St[S.top] = c; S.top++; } Node* pop_yufa(yufa_Stack &S){//出战 S.top--; return S.St[S.top]; } int o_youxianji(char o){//判断操作符的优先级 switch ( o ){ case '#': return 1; case '(' : return 2; case '|': return 3; case '+': return 4; case ')': return 5; case '*': return 6; default : return 0; //不是操作符 } } bool if_cat(char l,char r){//判断是否加入连接运算符 if(!o_youxianji(l)&&r=='(') //char+( return 1; else if(!o_youxianji(l)&&!o_youxianji(r)) //char+char return 1; else if(l==')'&&!o_youxianji(r)) //)+char return 1; else if(l=='*'&&!o_youxianji(r)) //*+char return 1; else if(l==')'&&r=='(') //)+( return 1; else if(l=='*'&&r=='(') //*+( return 1; else return 0; } string cin_Regular_Exp(){//输入正则表达式 cout<<"请输入正则表达式："; string R_exp; cin>>R_exp; R_exp.insert(0,"#"); R_exp.append("#"); //加入结束符 int l=0,r=1; while(R_exp[r]!='#'){ //将正则表达式加入cat连接符 if(if_cat(R_exp[l],R_exp[r])) R_exp.insert(l+1,"+"); l++;r++;} return R_exp; } bool if_high(char odd_op,char new_op){//比较运算符优先级 int odd_=o_youxianji(odd_op); int new_=o_youxianji(new_op); if(new_>odd_) return 1; return 0; } Node* Connect_Nodes(char op,yufa_Stack& char_st){//根据运算符连接节点 switch ( op ){ case '|': //双目运算符 return default_R_Node(op,pop_yufa(char_st),pop_yufa(char_st)); case '+': //双目运算符 return default_R_Node(op,pop_yufa(char_st),pop_yufa(char_st));; case '*': //单目运算符 return default_R_Node(op,pop_yufa(char_st),NULL); } } Tree_root Yufa_Tree(string exp){//构造语法树 op_Stack op_st;//符号栈 yufa_Stack char_st;//语法栈 Init_op_Stack(op_st); Init_yufa_Stack(char_st);//初始化语法栈和符号栈 push_op(op_st,exp[0]); for(int i = 1; i < exp.size()-1; i++){ char c = exp[i]; if(!o_youxianji(c)){ push_yufa(char_st,default_L_Node(c)); } else{ if(c == '('){ push_op(op_st,'(');//如果是（则直接入栈 } else if(c == ')'){//将遇到‘（’之间栈的内容清空 while(top_op(op_st) != '('){ char op = pop_op(op_st); push_yufa(char_st,Connect_Nodes(op,char_st)); } pop_op(op_st); } else if(c == '*'){ push_yufa(char_st,Connect_Nodes(c,char_st)); } else { while(!if_high(top_op(op_st),c)){//循环比较 char op = pop_op(op_st); push_yufa(char_st,Connect_Nodes(op,char_st)); } push_op(op_st,c); } } } while(top_op(op_st)!='#'){ char op = pop_op(op_st); push_yufa(char_st,Connect_Nodes(op,char_st)); } return char_st.St[char_st.bottom]; } int add_find_char(char *A,char a,int& size_){//在字符数组中加入新元素,若已经存在，则返回数组编号 if(size_==0) {A[0]=a;size_++;return Maxnum;} else{ int i; for(i=0;i<size_;i++) if(*(A+i)==a) return i; //找到了 不添加 A[i]=a;size_++; return Maxnum; //没找到，添加 } } //得到正则表达式的吸收符号 int Get_absorb_char(string exp,char *ab_chars){ int char_size = 0; for(int i=0;i<exp.size();i++){ if(!o_youxianji(exp[i])) //不是操作符 add_find_char(ab_chars,exp[i],char_size);} return char_size; } //状态集 typedef struct states_set{ int st_set[Maxnum]; int length=0;}; //图的矩阵表示 typedef struct Skips_graph{ int S_size;//状态数 int ab_char_size; //吸收字符种类数 char absorb_char[Maxnum]; //吸收字符 int Skips[Maxnum][Maxnum]; //状态跳转 int empty_Skips[Maxnum][Maxnum]; //空状态跳转 每行第一列放该状态的空跳转数 int start_S; //起点 int end_S; //终点(对nfa而言，只有一个终点) states_set end_set; //终点集(对于dfa而言，有多个终点) }; //初始化状态转移矩阵 void default_graph(Skips_graph &S,char *ab_char,int ab_char_size){ S.S_size=0; S.ab_char_size=ab_char_size; for(int i=0;i<ab_char_size;i++) S.absorb_char[i]=ab_char[i]; for(int i=0;i<Maxnum;i++) for(int j=0;j<Maxnum;j++) S.Skips[i][j]=Maxnum; //表示无跳转 for(int i=0;i<Maxnum;i++) S.empty_Skips[i][0]=0; //空跳转个数为0 } //添加新的状态跳转 图 起点 终点 吸收字符 void add_Skips(Skips_graph& S,int B,int E,char c){ int ab_char=add_find_char(S.absorb_char,c,S.ab_char_size); S.Skips[B][ab_char]=E; } void add_empty_Skips(Skips_graph& S,int B,int E){ S.empty_Skips[B][0]=S.empty_Skips[B][0]+1; //空跳转数加一 int size_=S.empty_Skips[B][0]; S.empty_Skips[B][size_]=E;} //构造叶子节点状态转移 void Leaf_Skip(Skips_graph& S,Node& N){ N.start_S=S.S_size;S.S_size++; N.end_S=S.S_size;S.S_size++; add_Skips(S,N.start_S,N.end_S,N.Char); //添加始末状态转移 } //构造根状态转移 void root_Skip(Skips_graph& S,Node& N){ //或根构造 if(N.type=='|'){ N.start_S=S.S_size;S.S_size++; N.end_S=S.S_size;S.S_size++; add_empty_Skips(S,N.start_S,N.lc->start_S); add_empty_Skips(S,N.start_S,N.rc->start_S); add_empty_Skips(S,N.lc->end_S,N.end_S); add_empty_Skips(S,N.rc->end_S,N.end_S);} //闭包构造 else if(N.type=='*'){ N.start_S=S.S_size;S.S_size++; N.end_S=S.S_size;S.S_size++; add_empty_Skips(S,N.start_S,N.lc->start_S); add_empty_Skips(S,N.start_S,N.end_S); add_empty_Skips(S,N.lc->end_S,N.lc->start_S); add_empty_Skips(S,N.lc->end_S,N.end_S);} //连接构造 else if(N.type=='+'){ N.start_S=N.lc->start_S; N.end_S=N.rc->end_S; add_empty_Skips(S,N.lc->end_S,N.rc->start_S);} else {cout<<"fault!";} } //递归构造NFA void NFA(Tree_root Tree, Skips_graph &S, string exp){ //构造状态转移矩阵