www.pudn.com > 69446611333.rar > compile_work2.cpp

#include "iostream.h" 
#include "string.h" 
 
////////////////////////////////////////////////////////////////////////// 
//////////////////   Begin Regular==>NFA  ////////////////////////////////  
  
struct Relation  //定义NFA中弧 
{ 
 int CurrentState;  //定义起始状态  
 int NextState;  //定义下一个状态 
 char TransitionElement;  //定义输入字符 
}; 
 
struct TokenState  //定义操作符号处理栈  
{ 
 int BeginState; //定义起始 
 int EndState;  //定义结束  
 int preposition; //定义记录（一个大的区域）状态开始时在波兰式中的位置 
}; 
 
int IsTransitionElement(char s)   //判断输入字符串是否合法  
{ 
 if (s=='0'||s=='1'||s=='$') 
	 return 1; 
 else return 0; 
} 
 
void NFADiagram(Relation *Rstring,int position,int CurrentState, 
				int NextState,char TransitionElement)  //生成NFA中弧的信息   
{ 
 Rstring[position].CurrentState=CurrentState; 
 Rstring[position].NextState=NextState; 
 Rstring[position].TransitionElement=TransitionElement; 
} 
 
int TokenDealing(char *string,int position,TokenState *token,int *Rtoken)//双目运算 
{ 
  
  
 if (IsTransitionElement(string[position]) //型如 “输入字符 输入字符 操作符” 
	 &&IsTransitionElement(string[position-1])) 
	 return 0; 
 else  if (IsTransitionElement(string[position])  //型如 “输入字符 操作符 输入字符” 
	       &&!IsTransitionElement(string[position-1])) 
	 return 1; 
 else   //查找在波兰式中区域的开始字符 
 { 
	 int firsttoken=token[Rtoken[position]].preposition; 
	 if(IsTransitionElement(string[firsttoken-1])) 
		 return 2;      //型如 “输入字符 |” 如果前一区域的结尾不存在* 
	 else return 3;     //如果前一区域的结尾存在* 
 } 
} 
 
int StarDealing(char *string,int position) 
{ 
 if(IsTransitionElement(string[position])) 
	 return 1; 
 else  
	 return 0; 
} 
 
Relation relation[25]; 
int relationi=0; 
 
void ToNFA(char *string) 
{ 
 //Relation relation[25];  
 TokenState token[20]; 
 int Rtoken[20];//记录字符串中操作符号在操作符号列中的位置 
 int tokeni=1; //定义操作符号在操作符号中的位置 
 //int relationi=0; 
 int secondtoken; 
 token[0].BeginState=0; 
 token[0].EndState=0; 
 for (unsigned i=0;iNFA ******"<=0) 
	   { 
        top--; 
    	while((stack[top]=='+' || stack[top]=='*') && top>=0) //将操作符号往前移动  
		{ 
         ReversePolishString[RPSi]=stack[top]; 
         top--; 
         RPSi++; 
		} 
	    top++; 
		stack[top]='+'; 
		top++; 
	   } 
	   ReversePolishString[RPSi]=statement[Si]; 
	   RPSi++; 
	   Si++; 
   } 
   else if (statement[Si]=='(') 
   { 
	   if ((statement[Si-1]=='0' || statement[Si-1]==')'  
		  || statement[Si-1]=='1'||statement[Si-1]=='$' 
		  || statement[Si-1] =='*') && Si-1>=0) 
	   { 
        top--; 
    	while((stack[top]=='+' || stack[top]=='*') && top>=0) 
		{ 
         ReversePolishString[RPSi]=stack[top]; 
         top--; 
         RPSi++; 
		} 
	    top++; 
		stack[top]='+'; 
		top++; 
	   } 
	   stack[top]=statement[Si]; 
       top++; 
	   Si++; 
   } 
   else if (statement[Si]==')') 
   { 
    top--; 
	while (stack[top]!='(') 
	{ 
      ReversePolishString[RPSi]=stack[top]; 
      top--; 
      RPSi++; 
	} 
	Si++; 
   } 
   else if (statement[Si]=='*') 
   {     
	top--; 
	while(stack[top]=='*' && top>=0) 
	{ 
      ReversePolishString[RPSi]=stack[top]; 
      top--; 
      RPSi++; 
	} 
	top++; 
	stack[top]=statement[Si]; 
	Si++; 
	top++; 
   } 
   else if (statement[Si]=='|') 
   { 
    top--; 
	while((stack[top]=='*' || stack[top]== '+' || stack[top]== '|') && top>=0) 
	{ 
      ReversePolishString[RPSi]=stack[top]; 
      top--; 
      RPSi++; 
	} 
	top++; 
	stack[top]=statement[Si]; 
	Si++; 
	top++; 
   } 
  } 
  top--; 
  while(top>=0) //将剩余操作符号串接到{0，1}*后边    
  { 
   ReversePolishString[RPSi]=stack[top]; 
   top--; 
   RPSi++; 
  } 
  ReversePolishString[RPSi]='\0'; 
} 
////////////////////    End Regular==>NFA	////////////////////////////// 
////////////////////////////////////////////////////////////////////////// 
 
////////////////////////////////////////////////////////////////////////// 
//////////////////   Begin NFA==>DFA  //////////////////////////////////// 
 
int c=0;//全局变量 
//temp 
void line(int s[],int n)//排序 
{ 
	for(int i=1;i0)&&(s[j] class stack 
{ 
	private: 
		int size; 
		int top; 
		Elem *listArray; 
	public: 
		stack(int sz=100) 
		{	size=sz;top=0;listArray=new Elem[sz];} 
		~stack() 
		{	delete []listArray;} 
		bool push(const Elem& item) 
		{ 
			if(top==size) return false; 
			else {listArray[top++]=item;return true;} 
		} 
		bool pop(Elem& it) 
		{ 
			if(top==0) return false; 
			else {it=listArray[--top];return true;} 
		} 
		int length() const {return top;} 
}; 
 
void closure(int s[][100],int& n,int z[],int n0,int sub[],int& subn)//数组的闭包 
{ 
	stackt; 
	int i=0; 
	for(int m=0;mt; 
	int i=0; 
	t.push(z); 
	sub[i++]=z; 
	int a,mark=0; 
	while(t.length ()) 
	{ 
		t.pop(a); 
		for(int j=0;jDFA   	////////////////////////////// 
////////////////////////////////////////////////////////////////////////// 
 
void main() 
{ 
    char statement[25], ReversePolishString[25]; 
    cout<<"请输入正则式( 注意对单个输入有*操作的时候要有$合成，比如求0*，要有($0)* ): "<>statement; 
    ToReversePolish(statement,ReversePolishString); 
    cout<DFA ******"<t; 
	t.push(dfa[0]);//初始状态的闭包入栈 
	while(t.length()) 
	{ 
		t.pop(temp); 
		for(i=0;i<2;i++) 
		{ 
			for(j=0;j0) 
        { 
		cout<<"DFA状态"<0) 
	  { 
		cout<0)  
			 cout<0) 
			 cout<