苏大编译原理实验二（构建NFA化至最简DFA）只用数组和栈

苏大编译原理实验二（构建NFA化至最简DFA）只用数组和栈

学习不好，数据结构课很遗憾没好好学，很遗憾很遗憾，所以不会用树也不会用列表，使用队列我更是自取其辱。。。。所以全篇只用到了数组和栈（以及最后的map）头文件引用得有点乱，对八起。

整体思路只要上学期认真上过编译原理课就应该明白，手动怎么画这里我们用电脑就怎么做，可以自己拿一个例子画一下复习复习。

需要的学弟学妹自取（注释基本都有，如果有什么不明白的我看到会回

然后如果需要的话这位大佬的写的超棒，虽然我没用，但是我先跪为敬。。。编译原理实验三：NFA确定化和DFA最小化_裕东方的博客-CSDN博客_nfa确定化和最小化

如果有大佬看见我的代码请帮忙改进一下！！！跪谢！

#include <iostream>
#include<string.h>
#include<stack>
#include<vector>
#include<map>
#define maxnum 100
using namespace std;
char putin[maxnum]="(a|b)*ab";
struct pointnode{int start[100];char trans[100];int end[100];
};
pointnode nfa[maxnum];
stack<char>charputin;
int beginnum=0;
int flag=0;
stack<int>doublepoint;
void createnfa(){int len=strlen(putin);int tempstrlen=0;for (int i=len-1;i>=0;--i){charputin.push(putin[i]);}while(!pty()){char tempchar&#p();char tempstr[maxnum];if(tempchar=='('){charputin.pop();p()!=')'){tempstr[tempstrlen]&#p();++tempstrlen;charputin.pop();}charputin.pop();flag=1;}else if (flag==1){if (tempchar=='*'){nfa[beginnum].start[0]=beginnum;nfa[beginnum].start[1]=beginnum;nfa[beginnum].trans[0]='*';nfa[beginnum].trans[1]='*';nfa[beginnum].end[0]=beginnum+1;nfa[beginnum].end[1]=beginnum+7;//={beginnum,'*',++beginnum};doublepoint.push(beginnum);++beginnum;flag=2;charputin.pop();}else{}nfa[beginnum].start[0]=beginnum;nfa[beginnum].trans[0]='*';nfa[beginnum].end[0]=beginnum+1;nfa[beginnum].start[1]=beginnum;nfa[beginnum].trans[1]='*';nfa[beginnum].end[1]=beginnum+3;doublepoint.push(beginnum);++beginnum;for(int i=0;tempstr[i];++i){if (tempstr[i]!='|'){nfa[beginnum].start[0]=beginnum;nfa[beginnum].trans[0]=tempstr[i];nfa[beginnum].end[0]=beginnum+1;++beginnum;}else{nfa[beginnum].start[0]=beginnum;nfa[beginnum].trans[0]='*';nfa[beginnum].end[0]=beginnum+3;++beginnum;}}nfa[beginnum].start[0]=beginnum;nfa[beginnum].trans[0]='*';nfa[beginnum].end[0]=beginnum+1;++beginnum;if(flag==2){nfa[beginnum].start[0]=beginnum;nfa[beginnum].trans[0]='*';nfa[beginnum].end[0]=beginnum+1;nfa[beginnum].start[1]=beginnum;nfa[beginnum].trans[1]='*';nfa[beginnum].end[1]=beginnum-5;doublepoint.push(beginnum);++beginnum;}flag=0;tempstrlen=0;}else if (tempchar=='*'){nfa[beginnum].start[0]=beginnum;nfa[beginnum].trans[0]=nfa[beginnum-1].trans[0];nfa[beginnum].end[0]=beginnum+1;nfa[beginnum-1].trans[0]='*';nfa[beginnum-1].trans[1]='*';nfa[beginnum-1].start[1]=beginnum-1;nfa[beginnum-1].end[1]=beginnum+2;doublepoint.push(beginnum-1);++beginnum;nfa[beginnum].start[0]=beginnum;nfa[beginnum].trans[0]='*';nfa[beginnum].end[0]=beginnum+1;nfa[beginnum].start[1]=beginnum;nfa[beginnum].trans[1]='*';nfa[beginnum].end[1]=beginnum-1;doublepoint.push(beginnum);++beginnum;charputin.pop();}else{nfa[beginnum].start[0]=beginnum;nfa[beginnum].trans[0]=tempchar;nfa[beginnum].end[0]=beginnum+1;++beginnum;charputin.pop();}}
}
bool ifdouble(int n){stack<int>tempstack;int flag=0;while(!pty()){p()!=n){tempstack.p());doublepoint.pop();}else{flag=1;break;}}while(!pty()){doublepoint.p());tempstack.pop();}if(flag==1){return true;}else{return false;}
}
//以上nfa完成，开始构造dfa。nfa节点总数为beginnum，查找是否是doublepoint为ifdouble()struct condi{int condinum[maxnum];int end[2];int num;
};
condi dfa[maxnum];
int dfalen=0;
condi c;
void search(int l,char ch);
bool ifincondinum(condi c1,int n);
int ifindfa(condi c2);
int ifintempdfa(condi c2);
void createdfa(){for(int l=0;l<dfalen;++l){c.num=0;search(l,'a');//添上a的关联部分int c1num1=ifindfa(c);//检查是否是重合状态if (c1num1==-1){//如果该状态和前面无重合，则给予编号并加入母节点的end中dfa[dfalen].num=c.num;for (int i=0;i<dfa[dfalen].num;i++){dfa[dfalen].condinum[i]&#dinum[i];}dfa[l].end[0]=dfalen;dfalen++;}else{//如果重合，则把重合的编号加入母节点end，并且把该状态删除dfa[l].end[0]=c1num1;}c.num=0;search(l,'b');int c2num1=ifindfa(c);if (c2num1==-1){dfa[dfalen].num=c.num;for (int i=0;i<dfa[dfalen].num;i++){dfa[dfalen].condinum[i]&#dinum[i];}dfa[l].end[1]=dfalen;dfalen++;}else{dfa[l].end[1]=c2num1;}}
}
void search0(){//找出初始状态的所有节点int num1=0;//nfa某个节点必有一个终点int num2=0;//nfa该节点可能有第二个终点for(int i=0;i<dfa[0].num;i++){if (nfa[dfa[0].condinum[i]].trans[0]=='*'){//如果该节点的中转为*num1=nfa[dfa[0].condinum[i]].end[0];if (!ifincondinum(dfa[0],num1)){//如果这是一个新的节点，则加入状态中dfa[0].condinum[dfa[0].num]=num1;dfa[0].num++; }}if(ifdouble(dfa[0].condinum[i])){//如果有两条支线，则看第二条线的内容if (nfa[dfa[0].condinum[i]].trans[1]=='*'){//同上num2=nfa[dfa[0].condinum[i]].end[1];if (!ifincondinum(c,num2)){dfa[0].condinum[dfa[0].num]=num2;dfa[0].num++;}}}}
}
void search(int l,char ch){//找出一个状态的所有节点int n=dfa[l].num;//本轮起始状态的节点数量int num1=0;//nfa某个节点必有一个终点int num2=0;//nfa该节点可能有第二个终点for(int i=0;i<n;++i){if (nfa[dfa[l].condinum[i]].trans[0]==ch or nfa[dfa[l].condinum[i]].trans[0]=='*' ){//如果该节点的中转之一为chnum1=nfa[dfa[l].condinum[i]].end[0];if (!ifincondinum(c,num1)){//如果这是一个新的节点，则加入状态中c.condinum[c.num]=num1;c.num++;}}if(ifdouble(dfa[l].condinum[i])){//如果有两条支线，则看第二条线的内容if (nfa[dfa[l].condinum[i]].trans[1]==ch or nfa[dfa[l].condinum[i]].trans[1]=='*'){//同上num2=nfa[dfa[l].condinum[i]].end[1];if (!ifincondinum(c,num2)){c.condinum[c.num]=num2;c.num++;}}}}n=c.num;for(int i=0;i<n;i++){if (dinum[i]].trans[0]=='*'){//如果该节点的中转为*num1=dinum[i]].end[0];if (!ifincondinum(c,num1)){//如果这是一个新的节点，则加入状态中c.condinum[c.num]=num1;c.num++;}}if(dinum[i])){//如果有两条支线，则看第二条线的内容if (dinum[i]].trans[1]=='*'){//同上num2=dinum[i]].end[1];if (!ifincondinum(c,num2)){c.condinum[c.num]=num2;c.num++;}}}}dinum+c.num);
}
bool ifincondinum(condi c1,int n){//检查该终点（节点）是否已经在该状态中int f=c1.num;for (int i=0;i<f;++i){if (c1.condinum[i]==n){return true;}}return false;
}
int ifindfa(condi c2){//检查是否在dfa中for(int i=0;i<dfalen;i++){if (dfa[i].num==c2.num){int j;for(j=0;j<dfa[i].num;j++){dinum[j]!=dfa[i].condinum[j]){break;}}if(j==dfa[i].num){return i;}}}return -1;
}
int jumpnum[maxnum];
int countjump=0;
int endnum[maxnum];
int countend=0;
bool injumpnum(int n){for(int k=0;k<countjump;++k){if (jumpnum[k]==n){return true;}}return false;
}
bool inendnum(int n){for(int k=0;k<countend;++k){if (endnum[k]==n){return true;}}return false;
}
void simplify(){for(int i=0;i<dfalen;++i){if (!ifincondinum(dfa[i],beginnum) and !injumpnum(i)){for(int j=i+1;j<dfalen;++j){if(dfa[j].end[0]==dfa[i].end[0]and dfa[j].end[1]==dfa[i].end[1] and (!ifincondinum(dfa[j],beginnum))){//将所有出现过的jumpnum都换掉for(int a=0;a<dfalen;++a){if( dfa[a].end[0]==j){dfa[a].end[0]=i;}else if (dfa[a].end[1]==j){dfa[a].end[1]=i;}}jumpnum[countjump]=j;//j会被跳过countjump++;}}}else if (ifincondinum(dfa[i],beginnum)){endnum[countend]=i;countend++;}}
}int main(){createnfa();dfa[dfalen].num=0;dfa[dfalen].condinum[0]=0;dfa[dfalen].num++;search0();//初始状态A完成，接下来二三搜索B,Csort(dfa[0].condinum,dfa[0].condinum+dfa[0].num);dfalen++;createdfa();//for(int i=0;i<dfalen;++i){//      cout<<i<<" a:"<<dfa[i].end[0]<<" b:"<<dfa[i].end[1]<<endl;//}simplify();map<int,char>asc;char prepareforuse[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};int ascnum=0;for(int i=0;i<dfalen;++i){if(!injumpnum(i)){asc.insert(pair<int,char>(i,prepareforuse[ascnum]));ascnum++;}}cout<<"以下为最简dfa"<<endl;for(int i=0;i<dfalen;++i){//cout<<i<<endl;if(!injumpnum(i)){cout<<asc[i]<<" a:"<<asc[dfa[i].end[0]]<<" b:"<<asc[dfa[i].end[1]]<<endl;}}int cinlen;cin>>cinlen;char cinchar[cinlen];cin>>cinchar;int getstart=0;for(int i=0;i<cinlen;++i){if(cinchar[i]=='a'){getstart=dfa[getstart].end[0];}else{getstart=dfa[getstart].end[1];}}if (inendnum(getstart)){cout<<"符合"<<endl;}else{cout<<"不符合"<<endl;}
}