THOMPSON 算法的实现

#include "Thompson.h" //主函数， void main() { string Regular_Expression = "(a|b)*abb"; cell NFA_Cell; Regular_Expression = "(a|b)*abb"; //接受输入 input(Regular_Expression);//调试需要先屏蔽 //添加“+”，便于转后缀表达式 Regular_Expression = add_join_symbol(Regular_Expression); //中缀转后缀 Regular_Expression = postfix(Regular_Expression); //表达式转NFA NFA_Cell = express_2_NFA(Regular_Expression); //显示 Display(NFA_Cell); } /**表达式转NFA处理函数,返回最终的NFA结合 */ cell express_2_NFA(string expression) { int length = expression.size(); char element; cell Cell,Left,Right; stack<cell> STACK; for(int i=0;i<length;i++) { element = expression.at(i); switch(element) { case '|': Right = STACK.top(); STACK.pop(); Left = STACK.top(); STACK.pop(); Cell = do_Unite(Left,Right); STACK.push(Cell); break; case '*': Left = STACK.top(); STACK.pop(); Cell = do_Star(Left); STACK.push(Cell); break; case '+': Right = STACK.top(); STACK.pop(); Left = STACK.top(); STACK.pop(); Cell = do_Join(Left,Right); STACK.push(Cell); break; default: Cell = do_Cell(element); STACK.push(Cell); } } cout<<"处理完毕!"<<endl; Cell = STACK.top(); STACK.pop(); return Cell; } //处理 a|b cell do_Unite(cell Left,cell Right) { cell NewCell; NewCell.EdgeCount=0; edge Edge1,Edge2,Edge3,Edge4; //获得新的新状态节点 state StartState = new_StateNode(); state EndState = new_StateNode(); //构建边 Edge1.StartState = StartState; Edge1.EndState = Left.EdgeSet[0].StartState; Edge1.TransSymbol = '#'; Edge2.StartState = StartState; Edge2.EndState = Right.EdgeSet[0].StartState; Edge2.TransSymbol = '#'; Edge3.StartState = Left.EdgeSet[Left.EdgeCount-1].EndState; Edge3.EndState = EndState; Edge3.TransSymbol = '#'; Edge4.StartState = Right.EdgeSet[Right.EdgeCount-1].EndState; Edge4.EndState = EndState; Edge4.TransSymbol = '#'; //构建单元 //先将Left和Right的EdgeSet复制到NewCell cell_EdgeSet_Copy(NewCell,Left); cell_EdgeSet_Copy(NewCell,Right); //将新构建的四条边加入EdgeSet NewCell.EdgeSet[NewCell.EdgeCount++] = Edge1; NewCell.EdgeSet[NewCell.EdgeCount++] = Edge2; NewCell.EdgeSet[NewCell.EdgeCount++] = Edge3; NewCell.EdgeSet[NewCell.EdgeCount++] = Edge4; //构建NewCell的启示状态和结束状态 NewCell.StartState = StartState; NewCell.EndState = EndState; return NewCell; } //处理 ab cell do_Join(cell Left,cell Right) { //将Left的结束状态和Right的开始状态合并，将Right的边复制给Left，将Left返回 //将Right中所有以StartState开头的边全部修改， for(int i=0;i<Right.EdgeCount;i++) { if(Right.EdgeSet[i].StartState.StateName.compare(Right.StartState.StateName)==0) { Right.EdgeSet[i].StartState = Left.EndState; STATE_NUM--; } else if(Right.EdgeSet[i].EndState.StateName.compare(Right.StartState.StateName)==0) { Right.EdgeSet[i].EndState = Left.EndState; STATE_NUM--; } } Right.StartState = Left.EndState; cell_EdgeSet_Copy(Left,Right); //将Left的结束状态更新为Right的结束状态 Left.EndState = Right.EndState; return Left; } //处理 a* cell do_Star(cell Cell) { cell NewCell; NewCell.EdgeCount=0; edge Edge1,Edge2,Edge3,Edge4; //获得新的新状态节点 state StartState = new_StateNode(); state EndState = new_StateNode(); //构建边 Edge1.StartState = StartState; Edge1.EndState = EndState; Edge1.TransSymbol = '#'; Edge2.StartState = Cell.EndState; Edge2.EndState = Cell.StartState; Edge2.TransSymbol = '#'; Edge3.StartState = StartState; Edge3.EndState = Cell.StartState; Edge3.TransSymbol = '#'; Edge4.StartState = Cell.EndState; Edge4.EndState = EndState; Edge4.TransSymbol = '#'; //构建单元 //先将Cell的EdgeSet复制到NewCell cell_EdgeSet_Copy(NewCell,Cell); //将新构建的四条边加入EdgeSet NewCell.EdgeSet[NewCell.EdgeCount++] = Edge1; NewCell.EdgeSet[NewCell.EdgeCount++] = Edge2; NewCell.EdgeSet[NewCell.EdgeCount++] = Edge3; NewCell.EdgeSet[NewCell.EdgeCount++] = Edge4; //构建NewCell的启示状态和结束状态 NewCell.StartState = StartState; NewCell.EndState = EndState; return NewCell; } //处理 a cell do_Cell(char element) { cell NewCell; NewCell.EdgeCount=0; edge NewEdge; //获得新的新状态节点 state StartState = new_StateNode(); state EndState = new_StateNode(); //构建边 NewEdge.StartState = StartState; NewEdge.EndState = EndState; NewEdge.TransSymbol = element; //构建单元 NewCell.EdgeSet[NewCell.EdgeCount++] = NewEdge; NewCell.StartState = NewCell.EdgeSet[0].StartState; NewCell.EndState = NewCell.EdgeSet[0].EndState;//EdgeCount此时为1 return NewCell; } /** */ void cell_EdgeSet_Copy(cell& Destination,cell Source) { int D_count = Destination.EdgeCount; int S_count = Source.EdgeCount; for(int i=0;i<S_count;i++) { Destination.EdgeSet[D_count+i] = Source.EdgeSet[i]; } Destination.EdgeCount = D_count + S_count; } /* 获得新的状态节点，统一产生，便于管理，不能产生重复的状态 并添加到state_set[]数组中 */ state new_StateNode() { state newState; newState.StateName = STATE_NUM+65;//转换成大写字母 STATE_NUM++; return newState; } //接收输入正规表达式，RegularExpression作为回传函数 void input(string &RegularExpression) { cout<<"请输入正则表达式： （操作符：() * |;字符集：a~z A~Z）"<<endl; do { cin>>RegularExpression; }while(!check_legal(RegularExpression)); //cout<<RegularExpression<<endl; } /**检测输入的正则表达式是否合法 */ int check_legal(string check_string) { if(check_character(check_string)&&check_parenthesis(check_string)) { return true; } return false; } /** 检查输入的字符是否合适 () * | a~z A~Z 合法返回true,非法返回false */ int check_character(string check_string) { int length = check_string.size(); for(int i=0;i<length;i++) { char check = check_string.at(i); if(is_letter(check))//小写和大写之间有5个字符，故不能连续判断 { //cout<<"字母 合法"; } else if(check=='('||check==')'||check=='*'||check=='|') { //cout<<"操作符 合法"; } else { cout<<"含有不合法的字符!"<<endl; cout<<"请重新输入:"<<endl; return false; } } return true; } /**先检查括号是否匹配 *合法返回true,非法返回false */ int check_parenthesis(string check_string) { int length = check_string.size(); char * check = new char[length]; strcpy(check,check_string.c_str()); //char a = check_string.at(1); stack<int> STACK; for(int i=0;i<length;i++) { if(check[i]=='(') STACK.push(i); else if(check[i]==')') { if(STACK.empty()) { cerr<<"有多余的右括号"<<endl;//暂时不记录匹配位置location cout<<"请重新输入:"<<endl; return false; } else STACK.pop(); } } if(!STACK.empty()) { //暂时不记录匹配位置location cerr<<"有多余的左括号"<<endl; cout<<"请重新输入:"<<endl; return false; } //cout<<check<<endl; return true; } /**检测是否是字母 是返回true,否则false */ int is_letter(char check) { if(check>='a'&&check<='z'||check>='A'&&check<='Z') return true; return false; } /**添加交操作符“+”，便于中缀转后缀表达式 例如 abb->a+b+b */ string add_join_symbol(string add_string) { /* 测试终止符\0 string check_string = "abcdefg\0aaa"; cout<<check_string<<endl; int length = check_string.size(); char * check = new char[2*length]; strcpy(check,check_string.c_str()); cout<<check<<endl; char *s = "ssss\0 aa"; cout<<s<<endl; string a(s); cout<<a<<endl; */ int length = add_string.size(); int return_string_length = 0; char *return_string = new char[2*length];//做多是两倍 char first,second; for(int i=0;i<length-1;i++) { first = add_string.at(i); second = add_string.at(i+1); return_string[return_string_length++] = first; //若第二个是字母、第一个不是'('、'|'都要添加 if(first!='('&&first!='|'&&is_l