DFA.rar_DFA_nfatodfa.cpp_正则式转换dfa_正则表达式 DFA

#include<iostream> using namespace std; #include<stack> #include<sstream> #include<vector> #include<queue> #include<set> #define error -1 typedef struct QNode{ //定义队列的接点 char elem; struct QNode *next; }QNode; typedef struct{ //6.定义队列 QNode *front; QNode *rear; }LinkQueue; int InitQueue(LinkQueue &Q){ //7.队列初始化 Q.front=Q.rear =(QNode*)malloc(sizeof(QNode));; if(!Q.front) return error; Q.front->next=NULL; return 1; } void EnQueue(LinkQueue &Q,char x){ //8.将元素x存入队列中 QNode *s; s=new QNode; s->elem =x; s->next =NULL; Q.rear->next=s; Q.rear =s; } char DeQueue(LinkQueue &Q){ //9.删除队头元素 if(Q.front ==Q.rear ) return error; else{ QNode *p=Q.front->next; char x=p->elem ; Q.front ->next =p->next ; if(p->next ==NULL) Q.rear =Q.front ; free(p); return x; } } char a[100];//状态数组 class DFA_Node; static DFA_Node* N1; static DFA_Node* N2; class NFA_Node; class Trans { public: char incept; NFA_Node* des; Trans(char incept,NFA_Node* des) { this->incept=incept; this->des=des; } }; class NFA_Node { public: int stateID; vector<Trans*> t; bool visit; NFA_Node(int stateID) { visit=false; this->stateID=stateID; } void AddTrans(Trans* tt) { t.push_back(tt); } }; class NFA { public: NFA_Node* start; NFA_Node* end; NFA(){} NFA(int SID,char c) { NFA_Node* s1=new NFA_Node(SID); NFA_Node* s2=new NFA_Node(SID+1); Trans* tt=new Trans(c,s2); s1->AddTrans(tt); start=s1; end=s2; } }; class Converter { public: int S_ID; Converter(string str) { pretreat(str); Houzhui(this->lamb); S_ID=1; } Converter(){S_ID=1;} void show() { cout<<this->lamb<<endl; } getcharnum(string ss) { int p=0; int num=ss.size(); char pc; for(int i=0; i<ss.size();i++){ pc=ss[i]; if(isOperator(pc)) { p++;} else{ a[i-p]=pc; } } num=num-p; cout<<"状态转移条件共有"<<num<<"个"<<endl; cout<<"他们分别是"<<endl; for(int j=0;j<num;j++){ cout<<a[j]<<" "; } cout<<endl; return num; } NFA ToNFA() { //stNFA.Clear(); //Operator_Stack.Clear(); NFA tempb,tempb1,tempb2; char tempc1; for(int i=0;i<lamb.size();i++) { tempc1 = lamb[i]; if (isOperator(tempc1)) { switch (tempc1) { case '|': tempb1 = stNFA.top(); stNFA.pop(); tempb2 = stNFA.top(); stNFA.pop(); tempb1=Union(tempb2,tempb1); stNFA.push(tempb1); break; case '&': tempb1 = stNFA.top(); stNFA.pop(); tempb2 = stNFA.top(); stNFA.pop(); tempb2=Connect(tempb1,tempb2); stNFA.push(tempb2); break; case '*': tempb1 = stNFA.top(); stNFA.pop(); tempb1=Closure(tempb1); stNFA.push(tempb1); break; } } else { tempb = NFA(S_ID,tempc1); S_ID+=2; stNFA.push(tempb); } } tempb = stNFA.top(); stNFA.pop(); return tempb; } private: stack<NFA> stNFA; stack<char> Operator_Stack; string lamb; bool isOperator(char c) { switch (c) { case '|': case '&': case '(': case ')': case '!': case '*': return true; default: return false; } } int getOperatorNumber(char t1) { switch (t1) { case '$': return 0; case '!': return 1; case ')': return 2; case '|': return 3; case '&': return 4; case '*': return 5; case '(': return 6; default: return 7; } } bool Operator_Less_Than(char t1, char t2) { int temp1 = getOperatorNumber(t1); int temp2 = getOperatorNumber(t2); if (temp1 <= temp2) return true; return false; } void pretreat(string str)//穿进去原始正则表达式 使ab变成a&b { int i=0; char c,pc; pc=str[i]; c=str[++i]; while(str[i]!='\0') { if(((pc==')'&&c=='('))||(!isOperator(pc)&&!isOperator(c))||(!isOperator(pc)&&c=='(')||(pc==')'&&!isOperator(c))||(pc=='*'&&!isOperator(c))||(pc=='*'&&c=='('))//四种情况需要加& str.insert(i,"&"); pc=str[i++]; c=str[i]; } str+="!"; this->lamb=str; } void Houzhui(string lamb) { string l=""; Operator_Stack.push('$'); char tempc,tempc2; for(int i=0;i<lamb.size();i++) { tempc = lamb[i]; if (isOperator(tempc)) { switch (tempc) { case '(': Operator_Stack.push(tempc); break; case ')': while (Operator_Stack.top() != '(') { tempc2 = Operator_Stack.top(); Operator_Stack.pop(); l += tempc2; } Operator_Stack.pop(); break; default : tempc2 = Operator_Stack.top(); while (tempc2!='('&&Operator_Less_Than(tempc,tempc2)) { tempc2 = Operator_Stack.top(); Operator_Stack.pop(); l += tempc2; tempc2 = Operator_Stack.top(); } Operator_Stack.push(tempc); break; } } else l += tempc; } this->lamb=l; cout<<"lamb is "<<lamb<<endl; } NFA& Connect(NFA G1, NFA G2) //把G1连在G2后面 { Trans* t=new Trans('@',G1.start); G2.end->AddTrans(t) ; G2.end = G1.end; return G2; } NFA& Union(NFA G1, NFA G2) //G1|G2 { NFA_Node* n1=new NFA_Node(S_ID++); Trans* t1=new Trans('@',G1.start); Trans* t2=new Trans('@',G2.start); n1->AddTrans(t1); n1->AddTrans(t2); NFA_Node* n2=new NFA_Node(S_ID++); Trans* t3=new Trans('@',n2); Trans* t4=new Trans('@',n2); G1.end