NFA到DFA的转换

这是一个可以实现正规式到NFA的转换，NFA 转换为DFA，DFA的最小化的程序

#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 *Rstringint positionint CurrentState
				int NextStatechar TransitionElement）  //生成NFA中弧的信息  
{
 Rstring[position].CurrentState=CurrentState;
 Rstring[position].NextState=NextState;
 Rstring[position].TransitionElement=TransitionElement;
}

int TokenDealing（char *stringint positionTokenState *tokenint *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 *stringint 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 {
  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（relationrelationi++token[tokeni].BeginState
                token[tokeni].EndState string[i-1]）;
	 // cout<<“5 “;
//对处理1*有问题。

	  NFADiagram（relationrelationi++token[tokeni].EndState
              token[tokeni].BeginState  ‘$‘）;
      NFADiagram（relationrelationi++token[tokeni].BeginState-1
              token[tokeni].EndState + 1  ‘$‘）;
      NFADiagram（relationrelationi++token[tokeni].BeginState-1
              token[tokeni].BeginState  ‘$‘）;
      NFADiagram（relationrelationi++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;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3489  2005-10-15 16:07  NFtoDFA\21codes.com.txt

     文件        588  2005-10-15 16:07  NFtoDFA\免费空间.txt

     文件       1946  2005-10-15 02:13  NFtoDFA\下载说明.txt

     文件      18450  2005-05-30 18:42  NFtoDFA\compile_work2.cpp

     文件       3485  2005-05-23 19:15  NFtoDFA\compile_work2.dsp

     文件        551  2005-05-23 19:16  NFtoDFA\compile_work2.dsw

     文件      58368  2008-01-19 03:23  NFtoDFA\compile_work2.ncb

     文件       1221  2008-01-19 03:23  NFtoDFA\compile_work2.plg

     目录          0  2007-05-04 23:52  NFtoDFA\Debug

     文件      53760  2008-01-19 03:23  NFtoDFA\compile_work2.opt

     目录          0  2007-05-04 23:52  NFtoDFA

----------- ---------  ---------- -----  ----

               142076                    12