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;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]);
	 // cout<<"5 ";
//对处理1*有问题。

	  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;


   }
   else   //处理型如 “操作符 操作符*”
   {
    token[tokeni].BeginState=token[tokeni-1].BeginState;
	token[tokeni].EndState=token[tokeni-1].EndState;
	token[tokeni].preposition=token[tokeni-1].preposition;
//	cout<<"6 ";
   
    
    NFADiagram(relation,relationi++,token[tokeni].EndState,
              token[tokeni].BeginState , '$');
    NFADiagram(relation,relationi++,token[tokeni-1].BeginState,
              token[tokeni].EndState + 1 , '$');
    NFADiagram(relation,relationi++,token[tokeni-1].BeginState,
              token[tokeni].BeginState , '$');
    NFADiagram(relation,relationi++,token[tokeni].EndState,
              token[tokeni].EndState+1 , '$');
    token[tokeni].BeginState = token[tokeni-1].BeginState;
    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]);
//			cout<<"1 ";
			break;
			//case 0:处理同10+类型即俩个输入字符
	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;  //对于整个区域而言 记录可能存在的*操作的其实状态，
//			cout<<"2 ";
			break;
            //case 1:同1+类型即一个输入字符
    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;
//			cout<<"3 ";
			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;
//			cout<<"4 ";
			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 , '$');
//			cout<<"7 ";
			break;
			//case 0:处理型如“输入字符 输入字符 |”
	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 , '$');
//			cout<<"8 ";
			break;
			//case 1:处理型如“+ 输入字符 |”
	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 , '$');
//		   cout<<"9 ";
		   break;
		   //case 2:处理型如“+ |”
	case 3:token[tokeni].EndState=token[tokeni-1].EndState+1;
		   secondtoken=token[Rtoken[i-1]].preposition-1;
           //secondtoken指俩处理前一区域中的结束字符在波兰式中位置
           //token[tokeni].BeginState=token[Rtoken[secondtoken]].BeginState-1;

		   if(token[Rtoken[secondtoken]].BeginState!=0)
		   { token[tokeni].BeginState=token[Rtoken[secondtoken]].BeginState-1;}
           else if(token[Rtoken[secondtoken]].BeginState==0)
		   { token[tokeni].BeginState=token[Rtoken[secondtoken]].BeginState;}

		    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 , '$');
//           cout<<"A ";
		   break;
		   //case 3:处理型如“+ |”
   }
   tokeni++;
  }
 }
 int compare=10000;
 for (int j=0;j<relationi;j++)
 {
  if(relation[j].CurrentState<compare)
	  compare=relation[j].CurrentState;
 }
 for (j=0;j<relationi;j++)
 {
   relation[j].CurrentState -= compare;
   relation[j].NextState -= compare;
 }
 cout<<"****** 正则式=====>NFA ******"<<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++;