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;i<strlen(string);i++)
 {
  if (string[i]=='*' || string[i]=='|' || string[i]=='$')
	  start=true;
 }
 for (i=0;i<strlen(string);i++)
 {
  if (string[i]=='*')
  {
   Rtoken[i]=tokeni;
   if (IsTransitionElement(string[i-1]))
   {
	  token[tokeni].BeginState=token[tokeni-1].EndState+1;
	  token[tokeni].EndState=token[tokeni].BeginState + 1;
	  token[tokeni].preposition = i-1;
	  NFADiagram(relation,relationi++,token[tokeni].BeginState,
                token[tokeni].EndState ,string[i-1]);
	  
        }
   else 
   {
    token[tokeni].BeginState=token[tokeni-1].BeginState;
	token[tokeni].EndState=token[tokeni-1].EndState;
	token[tokeni].preposition=token[tokeni-1].preposition;
   }
    
    NFADiagram(relation,relationi++,token[tokeni].EndState,
              token[tokeni].BeginState , '$');
    NFADiagram(relation,relationi++,token[tokeni].BeginState-1,
              token[tokeni].EndState + 1 , '$');
    NFADiagram(relation,relationi++,token[tokeni].BeginState-1,
              token[tokeni].BeginState , '$');
    NFADiagram(relation,relationi++,token[tokeni].EndState,
              token[tokeni].EndState+1 , '$');
   token[tokeni].BeginState = token[tokeni].BeginState -1 ;
   token[tokeni].EndState=token[tokeni].EndState + 1;
   tokeni++;
  }
  else if(string[i]=='+')
  {
   Rtoken[i]=tokeni;
   
   switch(TokenDealing(string,i-1,token,Rtoken))
   {
    case 0: token[tokeni].BeginState=token[tokeni-1].EndState+1;
			token[tokeni].EndState=token[tokeni].BeginState + 2;
			token[tokeni].preposition=i-2;
			
			NFADiagram(relation,relationi++,token[tokeni].BeginState,
                       token[tokeni].BeginState+1 , string[i-2]);
         	NFADiagram(relation,relationi++,token[tokeni].BeginState+1,
                       token[tokeni].EndState,string[i-1]);
			break;
	case 1: token[tokeni].BeginState=token[tokeni-1].EndState;
		    token[tokeni].EndState=token[tokeni].BeginState + 1;
			token[tokeni].preposition=token[tokeni-1].preposition;
			
			NFADiagram(relation,relationi++,token[tokeni].BeginState,
                       token[tokeni].EndState , string[i-1]);
			token[tokeni].BeginState=token[tokeni-1].BeginState;
			break;
    case 2: 
		    token[tokeni].BeginState=token[tokeni-1].BeginState-1;
		    token[tokeni].EndState=token[tokeni-1].BeginState;			
			token[tokeni].preposition=token[tokeni-1].preposition-1;

			NFADiagram(relation,relationi++,token[tokeni].BeginState,
                       token[tokeni].EndState , string[token[tokeni-1].preposition-1]);

			token[tokeni].EndState=token[tokeni-1].EndState;
			break;
	case 3: secondtoken=token[Rtoken[i-1]].preposition-1;
		    
		    token[tokeni].BeginState=token[Rtoken[secondtoken]].EndState;
			token[tokeni].EndState=token[tokeni-1].BeginState;
			token[tokeni].preposition=token[secondtoken].preposition;
            
		    NFADiagram(relation,relationi++,token[tokeni].BeginState,
                      token[tokeni].EndState , '$');
			token[tokeni].BeginState=token[Rtoken[secondtoken]].BeginState;
			token[tokeni].EndState=token[tokeni-1].EndState;
			break;
   }
   tokeni++;
  }
  else if(string[i]=='|')
  {
   Rtoken[i]=tokeni;
   switch(TokenDealing(string,i-1,token,Rtoken))
   {
    case 0: token[tokeni].BeginState=token[tokeni-1].EndState+1;
	    	token[tokeni].EndState=token[tokeni].BeginState + 5;
			token[tokeni].preposition=i-2;
			NFADiagram(relation,relationi++,token[tokeni].BeginState,
                       token[tokeni].BeginState+1 , '$');
         	NFADiagram(relation,relationi++,token[tokeni].BeginState+1,
                       token[tokeni].BeginState+2 , string[i-2]);
			NFADiagram(relation,relationi++,token[tokeni].BeginState,
                       token[tokeni].BeginState+3 , '$');
			NFADiagram(relation,relationi++,token[tokeni].BeginState+3,
                       token[tokeni].BeginState+4 , string[i-1]);
			NFADiagram(relation,relationi++,token[tokeni].BeginState+2,
                       token[tokeni].EndState , '$');
			NFADiagram(relation,relationi++,token[tokeni].BeginState+4,
                       token[tokeni].EndState , '$');
			break;
	case 1: token[tokeni].BeginState=token[tokeni-1].BeginState-1;
		    token[tokeni].EndState=token[tokeni-1].EndState+3;
			token[tokeni].preposition=token[tokeni-1].preposition;
			NFADiagram(relation,relationi++,token[tokeni].BeginState,
                       token[tokeni].BeginState+1 , '$');
			NFADiagram(relation,relationi++,token[tokeni].BeginState,
                       token[tokeni].EndState+1 , '$');
			NFADiagram(relation,relationi++,token[tokeni].EndState+1,
                       token[tokeni].EndState+2 , string[i-1]);
			NFADiagram(relation,relationi++,token[tokeni].EndState,
                       token[tokeni].EndState+3 , '$');
			NFADiagram(relation,relationi++,token[tokeni].EndState+2,
                       token[tokeni].EndState+3 , '$');
			break;
	case 2:token[tokeni].BeginState=token[tokeni-1].BeginState-1;
		   token[tokeni].EndState=token[tokeni-1].EndState+3;
           token[tokeni].preposition=token[Rtoken[i-1]].preposition-1; 
		   NFADiagram(relation,relationi++,token[tokeni].BeginState,
                      token[tokeni].BeginState+1 , '$');
		   NFADiagram(relation,relationi++,token[tokeni].BeginState,
                      token[tokeni].EndState-2 , '$');
		   NFADiagram(relation,relationi++,token[tokeni].EndState-2,
                      token[tokeni].EndState-1 , string[token[Rtoken[i-1]].preposition-1]);
		   NFADiagram(relation,relationi++,token[tokeni].EndState-1,
                      token[tokeni].EndState , '$');
		   NFADiagram(relation,relationi++,token[tokeni].EndState-3,
                      token[tokeni].EndState , '$');
		   break;
	case 3:token[tokeni].EndState=token[tokeni-1].EndState+1;
		   secondtoken=token[Rtoken[i-1]].preposition-1;

		    token[tokeni].BeginState=token[Rtoken[secondtoken]].BeginState-1;
		    NFADiagram(relation,relationi++,token[tokeni].BeginState,
                      token[Rtoken[secondtoken]].BeginState, '$');
			NFADiagram(relation,relationi++,token[tokeni].BeginState,
                      token[tokeni-1].BeginState , '$');
			NFADiagram(relation,relationi++,token[tokeni-1].EndState,
                      token[tokeni].EndState , '$');
			NFADiagram(relation,relationi++,token[Rtoken[secondtoken]].EndState,
                      token[tokeni].EndState , '$');

		   break;
		   
   }
   tokeni++;
  }
 }
 int compare=10000,max=-10000;
 for (int j=0;j<relationi;j++)
 {
  if(relation[j].CurrentState<compare)
	  compare=relation[j].CurrentState;
  if (relation[j].NextState>max)
	  max=relation[j].NextState;
 }
 for (j=0;j<relationi;j++)
 {
   relation[j].CurrentState -= compare;
   relation[j].NextState -= compare;
 }
 max -= compare;
 cout<<"初始状态为 : 0"<<endl
	 <<"终结状态为 : "<<max<<endl;
 if (start)
 cout<<"转换元素集合为 : 0,   1,   $"<<endl;
 else 
 cout<<"转换元素集合为 : 0,   1"<<endl;
 cout<<"状态集合从0至 "<<max<<" , "<<"总共 "<<max+1<<" 个状态"<<endl<<endl;
 for (j=0;j<relationi;j++)
 cout<<"从状态: "<<relation[j].CurrentState<<"          "
     <<"至状态  "<<relation[j].NextState<<"         "
	 <<"转换元素 :  "<<relation[j].TransitionElement<<endl;
}

void ToReversePolish(char *statement,char *ReversePolishString)
{
  int Si=0,top=0,RPSi=0;
  char stack[15];
  while(statement[Si]!='\0')
  {
   if (IsTransitionElement(statement[Si]))
   {
	   if ((statement[Si-1]=='0' || statement[Si-1]=='1' 
		  || statement[Si-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++;
	   }
	   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，(,),|,*,$)"<<endl;
 cin>>s;


 ToReversePolish(s,R);
 ToNFA(R);
}