正则分析的程序实现.doc

#include#include#includeusing namespace std;int NFASNum;/NFA状态数 vectorrec; string str2;int Accept100=0;/边类 class Edgepublic:int num;int pos;char weight;Edge *next;public: Edge() num = -1; pos = -1; next = NULL; Edge(int Num, int Pos, char ch) num= Num; pos = Pos; weight = ch; next = NULL; ;/ 顶点类 class Vertexpublic:int vnum;Vertex *next;Edge *out; public: Vertex() vnum = -1; next = NULL; out = NULL; Vertex(int num) vnum = num; next = NULL; out = NULL; ;/邻接表类 class AdjacentT private: Vertex *Start; int NumV; int NumE; public: AdjacentT() NumV = 1; NumE = 0; Start = new Vertex(); AdjacentT() Vertex *V; Edge *E; V = Start; for (int i=0; iout; while (E) V-out = E-next; delete E; E = V-out; V = V-next; int Getval(int pos)/得到顶点值 Vertex *V = Start; for (int i=0; inext; return V-vnum; int Getpos(int val)/得到顶点位置 Vertex *V = Start; int temp=-1; for (int i=0; ivnum = val) temp=i; break; V = V-next; return temp; char Getwei_pos(int v1, int v2)/得到边权值 char ch=$; Vertex *V = Start; for (int i=0; inext; Edge *E = V-out; while (E) if (E-pos = v2) ch=E-weight; break; else E = E-next; return ch; char Getwei_val(int val1, int val2) return Getwei_pos(Getpos(val1), Getpos(val2); int Setval(int val, int pos)/赋予顶点值 Vertex *V = Start; for (int i=0; inext; V-vnum = val; return 0; int Insertver(int val)/插入顶点值 int pos; pos = Getpos(val); Vertex *V = Start; while (V-next) V = V-next; Vertex *NewV = new Vertex(val); V-next = NewV; NumV+; return 0; int Insertedge_pos(int v1, int v2, char wei)/两定点之间插入边 Vertex *V = Start; for (int i=0; inext; Edge *E; E = V-out; Edge *NewE = new Edge(Getval(v2), v2, wei); if (! E) V-out = NewE; NumE+; return 0; while (E-pos != v2) & (E-next) E = E-next; if (! E-next) E-next = NewE; NumE+; return 0; int Insertedge_val(int val1, int val2, char wei) int v1 = Getpos(val1); int v2 = Getpos(val2); Insertedge_pos(v1, v2, wei); return 0; int Print_NFA()/输出 NFA Vertex *V = Start; Edge *E = new Edge(); cout 状态 边(权值) endl; for (int i=0; iNumV; i+) cout vnumout; if (E) while (E) cout num ( weight next; else cout ACC; cout next; return 0; int Print_DFA()/输出 DFA Vertex *V = Start; Edge *E = new Edge(); cout 状态 边(权值) 是否ACC endl; for (int i=0; iout; if (E) coutvnum ; while (E) cout num ( weight next; if(AcceptV-vnum=1) coutACC; coutnext; return 0; int* Closure(int *T)/闭包运算 int i = 0, j, k = 0, len = 0; int *temp = new int100; Vertex *V; Edge *E; while (Tlen != -1) len+; while (Ti != -1) int l; for (l=0; lk; l+) if (Ti = templ) break; if (l = k) tempk = Ti; k+; int pos = Getpos(Ti); V = Start; for (j=0; jnext; E = V-out; while (E) if (E-weight = ) for (l=0; lnum = templ) break; if (l = k) tempk = E-num; k+; Tlen+ = E-num; Tlen = -1; E = E-next; i+; /for(int i=0;Ti!=-1;i+) / coutTi ; / coutendl; tempk = -1; /for(int r=0;tempr!=-1;r+) / couttempr ; / rec.push_back(temp); / for(int i=0;irec.size();i+) / / for(int j=0;recij!=-1;j+) / coutrecij ; / /coutendl; return temp; ;struct Node int Start; int End; char Wei;/记录链表节点 vector p; vector pp;AdjacentT *NFA_T=new AdjacentT();AdjacentT *DFA_T=new AdjacentT();int GetRE(string Rexp) cout你输入的正则表达式是：Rexpendl; return 0;int SymbolPriority(char symbol)/算符优先级 int priority;switch (symbol)case |: priority = 1; break;case .: priority = 2; break;case *: priority = 3; break;default: priority = 0; break;return priority; string InsertCatNode(string Rexp)/插入连接运算符 int i = 0,len = Rexp.length(); string:iterator it=Rexp.begin();while (it!=Rexp.end()-1) if (*it!= ( & *it != . & *it != |) | *it = ) | *it = *)& (*(it+1) != ) & *(it+1) != . & *(it+1) != | & *(it+1) != *) Rexp.insert(it+1,.); len = Rexp.length(); it=Rexp.begin();i+; it=it+i;cout 加入连结点: Rexp endl; return Rexp;int GetAlphabet(string str)/的到字母集合 string str1; for(int i=0;istr.length();i+) if(stri!=*&stri!=|&stri!=.&stri!=(&stri!=) str1+=stri; bool flag=false; for(int i=0;istr1.length();i+) for(int j=0;ji;j+) if(str1j=str1i) flag=true; break; else flag=false; if(flag=false) str2+=str1i; cout字母表为:str2endl; return 0;string GerRegExpToPost(string Rexp)/得到逆波兰式 int i=0; int j=0; stacks; string strpost; s.push($); char ch1,ch2; ch1=Rexpi; while(ch1!=0) if (ch1=()s.push(ch1);ch1=Rexp+i;else if(ch1=)while(s.top()!=()strpost+=s.top();s.pop(); s.pop();ch1=Rexp+i;else if(ch1=|)|(ch1=*)|(ch1=.) ch2=s.top(); while (SymbolPriority(ch2) =SymbolPriority(ch1) strpost+= ch2; s.pop(); ch2=s.top();s.push(ch1);ch1=Rexp+i;elsestrpost+=ch1;ch1=Rexp+i;/coutstrpostendl;ch1=s.top();s.pop();while(ch1=|)|(ch1=*)|(ch1=.)strpost+= ch1;ch1=s.top();s.pop();cout 转为后缀式: strpost endl; return strpost;int ThompsonConstrucNFA(string Rexp)/构造NFA int i, j;char ch;int s1, s2;stacks;NFA_T-Setval(0, 0);i = 1;j = 0;ch = Rexpj; while (ch!=0)if (ch = .)s2 = s.top();s.pop();int temp1 = s.top();s.pop();int temp2 = s.top();s.pop();s1 = s.top();s.pop();NFA_T-Insertedge_val(temp2, temp1, );s.push(s1);s.push(s2);else if (ch = |)s2 = s.top();s.pop();int temp1 = s.top();s.pop();int temp2 = s.top();s.pop();s1 = s.top();s.pop();NFA_T-Insertver(i);NFA_T-Insertver(i+1);NFA_T-Insertedge_val(i, s1, );NFA_T-Insertedge_val(i, temp1, );NFA_T-Insertedge_val(temp2, i+1, );NFA_T-Insertedge_val(s2, i+1, );s1 = i;s2 = i+1;s.push(s1);s.push(s2);i += 2;else if (ch = *)s2 = s.top();s.pop();s1 = s.top();s.pop();NFA_T-Insertver(i);NFA_T-Insertver(i+1);NFA_T-Insertedge_val(i, i+1, );NFA_T-Insertedge_val(s2, s1, );NFA_T-Insertedge_val(i, s1, );NFA_T-Insertedge_val(s2, i+1, );s1 = i;s2 = i+1; s.push(s1);s.push(s2);i += 2;else Node N;NFA_T-Insertver(i);NFA_T-Insertver(i+1);NFA_T-Insertedge_val(i, i+1, ch);N.Start=i;N.End=i+1;N.Wei=ch;p.push_back(N);s1 = i;s2 = i+1; s.push(s1);s.push(s2);i += 2;j+;ch = Rexpj;s2 = s.top(); s.pop(); s1 = s.top();s.pop();NFA_T-Insertedge_val(0, s1, );NFASNum = s2 + 1;NFA_T-Print_NFA();return 0;bool cmp(vectors,vectorv) for(int i=0;iv.size();i+) if(vi!=si) return true; return false; int CmpArray(vector t1, int *t2) vectors; vectorv; for(int i=0;t2i!=-1;i+) s.push_back(t2i); int flagrec.size(); for(int r=0;rrec.size();r+) v.clear(); for(int k=0;recrk!=-1;k+) v.push_back(recrk); if(v.size()=s.size() if(cmp(v,s) flagr=1; else flagr=0; else flagr=1; for(int i=0;irec.size();i+) if(flagi=0) return i; return -1;int SubSetConstruction()/构造DFA vectorq; int T1000; T0=0; T1=-1; rec.push_back(NFA_T-Closure(T); int k=0; for(int k=0;krec.size();k+) for(int i=0;istr2.length();i+) for(int j=0;jp.size();j+) if(str2i=pj.Wei) for(int r=0;reckr!=-1;r+) /coutreckr-pj.Startendl; if(reckr=pj.Start) q.push_back(pj.End); for(int l=0;lq.size();l+) Tl=ql; / coutqi=TiClosure(T); /cout+tempClosure(T)=-1&NFA_T-Closure(T)0!=-1) rec.push_back(NFA_T-Closure(T); DFA_T-Insertver(k); DFA_T-Insertver(rec.size()-1); DFA_T-Insertedge_val(k, rec.size()-1, str2i); / coutaaaaaaaaaaaaaaaClosure(T)!=-1&NFA_T-Closure(T)0!=-1) DFA_T-Insertver(k); DFA_T-Insertver(temp); DFA_T-Insertedge_val(k,temp,str2i); N.Start=k; / coutbbbbbbbbbbbbbendl; N.End=temp; /cout-+Closure(T)endl; /cout+N.Endendl; N.Wei=str2i; pp.push_back(N); q.clear(); for(int i=0;irec.size();i+) coutDFA状态集i: ; for(int j=0;recij!=-1;j+) if(recij=NFASNum-1) Accepti=1; coutrecij