THOMPSON算法的實(shí)現(xiàn)

1、實(shí)驗(yàn)二：THOMPSO算法的實(shí)現(xiàn)掌握THOMPSC算法原理和方法。二. 實(shí)驗(yàn)要求、內(nèi)容及步驟1. 輸入字母表上的正規(guī)式r，輸出一個(gè)接受L (r )的NFA2. 采用C+語言，實(shí)現(xiàn)該算法；3. 編制測試程序4. 調(diào)試程序;三. 實(shí)驗(yàn)設(shè)備計(jì)算機(jī)、Windows操作系統(tǒng)、Visual C+程序集成環(huán)境。四. 實(shí)驗(yàn)原理Thomp sor構(gòu)造法：從正規(guī)表達(dá)式構(gòu)造NFA輸入：字母表2上的一個(gè)正規(guī)表達(dá)式輸出：接受L(r)的NFA N使用下面的規(guī)則1和2為r的每個(gè)方法：將r分解成最基本的子表達(dá)式，基本符號(£或2中的符號)構(gòu)造NFA用規(guī)則3逐步組合前面構(gòu)造的NFA 直到獲得整個(gè)正規(guī)表達(dá)式的 NFA為

2、止。規(guī)則1.對£ ,構(gòu)造NFA這里i是新的開始狀態(tài)，f是新的接受狀態(tài)。很明顯這個(gè)NFA識別汀。 規(guī)則2.對于2中的每個(gè)符號a,構(gòu)造NFA同樣，i是新的開始狀態(tài)，f是新的接受狀態(tài)。這個(gè)NFA識別a 0規(guī)則3 .如果N(s)和對于正規(guī)表達(dá)式S*,構(gòu)造復(fù)合的NFA Ns*):N(t)是正規(guī)表達(dá)式S和t的NFA則：對于括起來的正規(guī)表達(dá)式(S), 使用N ( S)本身作為它的NFA在構(gòu)造過程中，每次構(gòu)造的新狀態(tài)都要賦予不同的名字。這樣，任何NFA的兩個(gè)狀態(tài)都具有不同的名字。即使同一符號在 r中出現(xiàn)多次，我們也要為該 符號的每個(gè)實(shí)例創(chuàng)建一個(gè)獨(dú)立的帶有自己狀態(tài)的 NFA五. 程序設(shè)計(jì)框架六. 程序

3、流程圖七.實(shí)驗(yàn)代碼核心代碼如下:#ifndef THO MP SON_H #defi ne THI MP SON_H #in elude <iostream> #in clude <stdio.h> #in clude <stack> #in clude <stri ng> using n ames pace std;#defi ne MAX 100節(jié)點(diǎn)，定義成結(jié)構(gòu)體，便于以后擴(kuò)展struct statestri ng StateName;邊空轉(zhuǎn)換符永#'表示struct edgestate StartState;state En dSt

4、ate; char Tran sSymbol; ;單元struct celledge EdgeSetMAX; int EdgeCo unt;state Startstate; state En dState;；全局變量聲明/int EDGE_NUM = 0;int STATE_NUM = 0;/int CELL_NUM = 0;函數(shù)聲明void inpu t(stri ng&);int check_legal(stri ng);int check_character(stri ng);int check_ paren thesis(stri ng);int is_letter(char

5、);stri ng add_j oin _symbol(stri ng);中綴轉(zhuǎn)后綴-stri ng po stfix(stri ng);優(yōu)先級 in stack p riorityint isp( char);優(yōu)先級 in coming p riorityint scp( char);表達(dá)式轉(zhuǎn)NFAcell exp ress_2_NFA(stri ng);處理a|bcell do_U ni te(cell,cell);處理abcell do_Jo in( cell,cell);處理a*cell do_Star(cell);處理acell do_Cell(char);將一個(gè)單元的邊的集合復(fù)制到

6、另一個(gè)單元void cell_EdgeSet_Co py(cell & ,cell);產(chǎn)生一個(gè)新的狀態(tài)節(jié)點(diǎn)，便于管理state new_StateNode();顯示void Dis play(cell);#e ndif#in clude "Tho mpson .h"主函數(shù)，void mai n()stri ng Regular_Ex pressi on = "(a|b)*abb"cell NFA_Cel|-Regular_Ex pressi on = "(a|b)*abb"接受輸入input(Regular_Expressio

7、n);/ 調(diào)試需要先屏蔽/添加“ + ”屜于轉(zhuǎn)后綴表達(dá)式Regular_Ex pressi on = add_join_symbol(Regular_Ex pressi on);中綴轉(zhuǎn)后綴Regular_Ex pressi on = po stfix(Regular_Ex pressi on);/表達(dá)式轉(zhuǎn)NFA-NFA_Cell = ex press_2_NFA(Regular_Ex pressio n);/顯示Dis play(NFA_Cell);/*表達(dá)式轉(zhuǎn)NFA處理函數(shù)，返回最終的NFA結(jié)合*/cell exp ress_2_NFA(stri ng exp ressi on) "

8、;"int len gth = exp ressi on. size();char eleme nt;cell Cell,Left,Right;stack<cell> STACK;for(i nt i=0;i<le ngth;i+)eleme nt = exp ressi on. at(i);switch(eleme nt)case T：Right = STACK.to p();STACK .pop();Left = STACK.to p();STACK .pop();Cell = do_U nite(Left,Right);STACK. push(Cell);br

9、eak;case '*':Left = STACK.to p();STACK .pop();Cell = do_Star(Left);STACK. push(Cell);break;case '+':Right = STACK.to p();STACK .pop();Left = STACK.to p();STACK .pop();Cell = do_Joi n(Left,Right);STACK. push(Cell); break;default:Cell = do_Cell(eleme nt);STACK.push(Cell);cout<<&q

10、uot;處理完畢!"<<endl;Cell = STACK.t op();STACK .pop(); return Cell;處理a|bcell do_Un ite(cell Left,cell Right)"cell NewCell;NewCell.EdgeCou nt=O; edge Edge1,Edge2,Edge3,Edge4;/獲得新的新狀態(tài)節(jié)點(diǎn)state StartState = n ew_StateNode();state En dState = new_StateNode();/構(gòu)建邊Edge1.StartState = StartState;E

11、dge1.E ndState = Left.EdgeSet0.StartState;Edge1.Tra nsSymbol = '#'Edge2.StartState = StartState;Edge2.E ndState = Right.EdgeSetO.StartState;Edge2.Tra nsSymbol = '#'Edge3.StartState = Left.EdgeSetLeft.EdgeCou nt-1.E ndState;Edge3.E ndState = En dState;Edge3.Tra nsSymbol = '#'E

12、dge4.StartState = Right.EdgeSetRight.EdgeCou nt-1.E ndState;Edge4.E ndState = En dState;Edge4.Tra nsSymbol = '#'/構(gòu)建單元/先將 Left 和 Right 的 EdgeSet 復(fù)制到 NewCell cell_EdgeSet_Co py(NewCell,Left);cell_EdgeSet_C op y(NewCell,Right);將新構(gòu)建的四條邊加入EdgeSetNewCell.EdgeSetNewCell.EdgeCou nt+ = Edge1;NewCell.

13、EdgeSetNewCell.EdgeCou nt+ = Edge2;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge3;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge4; /構(gòu)建NewCell的啟示狀態(tài)和結(jié)束狀態(tài)NewCell.StartState = StartState;NewCell.E ndState = En dState; return NewCell;處理abcell do_Joi n( cell Left,cell Right)將Left的結(jié)束狀態(tài)和 Right的開始狀態(tài)合并，將Right的邊復(fù)制給Left

14、，將Left返回將Right中所有以StartState開頭的邊全部修改，for(i nt i=0;i<Right.EdgeCou nt;i+)if(Right.EdgeSeti.StartState.StateN pare(Right.StartState.StateName)=O) Right.EdgeSeti.StartState = Left.E ndState;STATE_NUM-;elseif(Right.EdgeSe ti.E ndState.StateName.co mp are(Right.StartState.StateName)=O)Right.EdgeSeti.E

15、 ndState = Left.E ndState; STATE_NUM-;Right.StartState = Left.E ndState;cell_EdgeSet_Co py(Left,Right);將Left的結(jié)束狀態(tài)更新為 Right的結(jié)束狀態(tài)Left.E ndState = Right.E ndState; return Left;處理a*cell do_Star(cell Cell)cell NewCell;NewCell.EdgeCou nt=O; edge Edge1,Edge2,Edge3,Edge4;/獲得新的新狀態(tài)節(jié)點(diǎn)state StartState = n ew_St

16、ateNode(); state En dState = n ew_StateNode();/構(gòu)建邊Edge1.StartState = StartState;Edge1.E ndState = En dState;Edge1.Tra nsSymbol = '#'Edge2.StartState = Cell.E ndState;Edge2.E ndState = Cell.StartState;Edge2.Tra nsSymbol = '#'Edge3.StartState = StartState;Edge3.E ndState = Cell.StartSt

17、ate;Edge3.Tra nsSymbol = '#'Edge4.StartState = Cell.E ndState;Edge4.E ndState = En dState;Edge4.Tra nsSymbol = '#'/構(gòu)建單元/先將 Cell 的 EdgeSet 復(fù)制到 NewCellcell_EdgeSet_Co py(NewCell,Cell);將新構(gòu)建的四條邊加入EdgeSetNewCell.EdgeSetNewCell.EdgeCou nt+ = Edge1;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge2

18、;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge3;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge4;/構(gòu)建NewCell的啟示狀態(tài)和結(jié)束狀態(tài)NewCell.StartState = StartState;NewCell.E ndState = En dState; return NewCell;處理acell do_Cell(char eleme nt)"cell NewCell;NewCell.EdgeCou nt=O;edge NewEdge;/獲得新的新狀態(tài)節(jié)點(diǎn)state StartState = n e

19、w_StateNode();state En dState = new_StateNode();/構(gòu)建邊NewEdge.StartState = StartState;NewEdge.E ndState = En dState;NewEdge.Tra nsSymbol = eleme nt;/構(gòu)建單元NewCell.EdgeSetNewCell.EdgeCou nt+ = NewEdge;NewCell.StartState = NewCell.EdgeSet0.StartState;NewCell.E ndState = NewCell.EdgeSet0.E ndState;/EdgeCou

20、 nt 此時(shí)為 1 return NewCell;void cell_EdgeSet_C opy( cell& Desti nati on, cell Source)" "int D_co unt = Dest in ati on .EdgeCo unt; int S_co unt = Source.EdgeCo unt;for(i nt i=0;i<S_co un t;i+)Dest in ati on .EdgeSetD_co un t+i = Source.EdgeSeti;Desti nati on .EdgeCo unt = D_co unt + S

21、_co unt;/*獲得新的狀態(tài)節(jié)點(diǎn)，統(tǒng)一產(chǎn)生，便于管理，不能產(chǎn)生重復(fù)的狀態(tài)并添加到state_set數(shù)組中*/state new_StateNode() "state n ewState;newState.StateName = STATE_NUM+65;/ 轉(zhuǎn)換成大寫字母 STATE_NUM+;return n ewState;接收輸入正規(guī)表達(dá)式，RegularExpression作為回傳函數(shù) void inpu t(stri ng &RegularEx pressi on)（操作符：（）* |;字符集：az AZ） "<<endl; cout<

22、;<"請輸入正則表達(dá)式： docin> >RegularEx pressio n; while(!check_legal(RegularEx pressi on); /coutvvRegularEx pressi on<<en dl;/*檢測輸入的正則表達(dá)式是否合法*/int check_legal(stri ng check_stri ng)" "if(check_character(check_stri ng)&&check_ paren thesis(check_stri ng) " "一 &

23、quot;return true;return false;/*檢查輸入的字符是否合適()* | az AZ合法返回true,非法返回false*/int check_character(stri ng check_stri ng)" "int len gth = check_stri ng.size();for(i nt i=0;i<le ngth;i+)char check = check_stri ng.at(i);if(is_letter(check)/小寫和大寫之間有5個(gè)字符，故不能連續(xù)判斷/cout<<"字母合法"else

24、if(check='('|check=')'|check='*'|check=T)/cout<<"操作符 合法"elsecout<<"含有不合法的字符!"<<endl;cout<<"請重新輸入:"<<endl;return false;return true;/*先檢查括號是否匹配*合法返回true,非法返回false*/int check_ paren thesis(stri ng check_stri ng) "

25、"int len gth = check_stri ng.size(); char * check = new charle ngth; strc py (check,check_stri ng.c_str(); /char a = check_stri ng.at(1); stack <in t> STACK;for(i nt i=0;i<le ngth;i+) if(checki='(')STACK. push(i); else if(checki=')') if(STACK.e mp ty()cerr<<"

26、有多余的右括號"<<endl;/暫時(shí)不記錄匹配位置locationcout<<"請重新輸入:"<<endl;return false; elseSTACK. pop();if(!STACK.e mp ty()/暫時(shí)不記錄匹配位置locationcerr<<"有多余的左括號"<<endl; cout<<"請重新輸入:"<<endl; return false;/cout<<check<<e ndl; return tru

27、e;/*檢測是否是字母是返回true,否則false*/int is_letter(char check)if(check>='a '&&check<='z'|check>='A '&&check<='Z') return true;return false;/*添加交操作符“ + ”，便于中綴轉(zhuǎn)后綴表達(dá)式 例如 abb->a+b+b*/stri ng add_j oin _symbol(stri ng add_stri ng) " "/* 測試終止

28、符0stri ng check_stn ng = "abcdefg'Oaaa" cout<<check_stn ng<<e ndl;int len gth = check_stri ng.size();char * check = new char2*le ngth; strc py (check,check_stn ng.c_str(); cout<<check<<e ndl;char *s = "ssssO aa"cout<<s<<e ndl;stri ng a(s);c

29、out<<a<<e ndl;*/int len gth = add_stri ng.size();int return_stri ng_len gth = 0;char *return_string = new char2*length;/ 做多是兩倍 char first,sec ond;for(i nt i=0;i<le ngth-1;i+)first = add_stri ng.at(i);sec ond = add_stri ng.at(i+1);retur n_stn ngretur n_stn ng_le ngth+ = first;/若第二個(gè)是字母、

30、第一個(gè)不是('、I'都要添加if(first!='('&&first!=T&&is_letter(seco nd)retur n_stri ngretur n_stri ng_le ngth+ = '+' " ""/若第二個(gè)是'(',第一個(gè)不是T、(',也要加else if(seco nd='('&&first!='|'&&first!='(')retur n_stri ngretu

31、r n_stri ng_le ngth+ = '+' " ""將最后一個(gè)字符寫入retur n_stri ngretur n_stri ng_le ngth+ = sec ond; retur n_stri ngretur n_stri ng_le ngth = '0' stri ng STRING(return_stri ng);cout<<"加'+'后的表達(dá)式："<<STRING<<endl; return STRING;/*優(yōu)先級表：#0isp icp *

32、/in stack p riority int isp( char c) switch(c)case '#': retur n 0;棧內(nèi)優(yōu)先級0case '(': retur n 1;case '*': return 7;case T： return 5;case '+': retur n 3;case ')': retur n 8;/若走到這一步，說明出錯(cuò)了 cerr<<"ERROR!"<<e ndl;return false;/in coming p riority

33、棧外優(yōu)先級 int icp( char c)switch(c)case '#': return 0;case '(': retur n 8;case '*': return 6;case T： return 4;case '+': retur n 2;case ')': retur n 1;/若走到這一步，說明出錯(cuò)了cerr<<"ERROR!"<<e ndl; return false;/*中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式*/stri ng po stfix(stri ng e)/

34、設(shè)定e的最后一個(gè)符號式“ #”，而其“ #”一開始先放在棧s的棧底 e = e+"#"stack<char> s;char ch = '#',ch1, op;s.pu sh(ch);/讀一個(gè)字符stri ng out_stri ng =""int read_locati on = 0;ch = e.at(read_locati on+); while(!s.e mp ty()if(is_letter(ch)out_stri ng = out_stri ng + ch; /cout<<ch;ch = e.at(rea

35、d_locatio n+);else/cout<<"輸出操作符："<<ch<<endl;ch1 = s.t op();if(is p(ch1)<ic p( ch)s.pu sh(ch);/cout<<"壓棧"<<ch<<"讀取下一個(gè)"<<endl; ch = e.at(read_locati on+); "else if(is p(ch1)>ic p(ch)op = s.to p();s.popO;/cout<<"退棧"<<op<<"添加到輸出字符串 "<<endl; out_stri ng = out_stri ng + op;/cout< <op; elseop = s.to p();s.popO；/cout<<"退棧"<<op<<"但不添加到輸入字符串"<<endl;if(op='(')ch = e.at(read_locati on+);/cout<<e ndl;cout<<"