www.pudn.com > ToNfa.rar > toNFA.cpp

#include "iostream.h" 
#include "string.h" 
 
class Relation 
{ 
public: 
 int CurrentState; 
 int NextState; 
 char TransitionElement; 
}; 
 
class TokenState 
{ 
public: 
 int BeginState; 
 int EndState; 
 int preposition; 
}; 
 
int IsTransitionElement(char s) 
{ 
 if (s=='0'||s=='1'||s=='$'||s=='('||s==')'||s=='*') 
	 return 1; 
 else return 0; 
} 
 
void NFADiagram(Relation *Rstring,int position,int CurrentState, 
				int NextState,char TransitionElement) 
{ 
 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; 
 } 
} 
 
void ToNFA(char *string) 
{ 
 Relation relation[25];  
 TokenState token[20]; 
 int Rtoken[20]; 
 int tokeni=1,relationi=0; 
 int secondtoken; 
 bool start=false; 
 token[0].BeginState=0; 
 token[0].EndState=0; 
 for (unsigned i=0;imax) 
	  max=relation[j].NextState; 
 } 
 for (j=0;j=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) 
  { 
   ReversePolishString[RPSi]=stack[top]; 
   top--; 
   RPSi++; 
  } 
  ReversePolishString[RPSi]='\0'; 
} 
 
 
 
void main() 
{ 
 char s[25], R[25]; 
 
 cout<<"请输入正则表达式 : (可以输入的符号：0，1，(,),|,*,$)"<>s; 
 
 
 ToReversePolish(s,R); 
 ToNFA(R); 
}