autom.cpp

NFA自动机的实验

// Autom.cpp: implementation of the Autom class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
//#include "AutomTest.h"
#include "Autom.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
//#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Autom::Autom()
{
	Init();
//	cout<<"Autom is init!";	
}

Autom::~Autom()
{
//	cout<<"Autom is delete!";	
}

bool Autom::InitFormFile(string str)		//从文附件初始化状态转移表
{
	Init();

	ifstream in(str.c_str());
	int iLine=0, iColumn=0;		//记录状态表行
	char chrsTemp[ CHRCOLUMNS ];
	memset(chrsTemp,0, CHRCOLUMNS *sizeof(char));

	iLine=0;
	iColumn=0;
//处理表头，格式形如 \tA\tB...,专题换为\AB...存储
	if ( !in.getline(chrsTemp, CHRCOLUMNS ) ) 
	{
		return false;
	}
	statesTable[iLine][iColumn][ 0 ] = '\\';
	iColumn=1;
	for(int j=0;j <  CHRCOLUMNS  ; j++)
	{
		char chr=chrsTemp[j] ;
		if( chr == 0 )break;	//此行结束
		if( chr == '\t' )
			continue;
		else
		{
			statesTable[iLine][iColumn][ 0 ] = chr;
			iColumn++;
		}
	}
	columnTable=iColumn-1;//记录状态表的列数


	iLine=0;
	for(int m=iLine; m < LINES ; m++)
	{
//		for(int i=0; i < CHRCOLUMNS ; i++)
		{
			iColumn=0;
			memset(chrsTemp,0, CHRCOLUMNS *sizeof(char));
			
			if ( !in.getline(chrsTemp, CHRCOLUMNS ) ) 
			{
				break;
			}
			iLine++;
			
			
			string strTemp;
			for(int j=0;j< CHRCOLUMNS ;j++)
			{
				char chr=chrsTemp[j] ;
				if ( chr == 0 )
				{
				
					if( !strTemp.empty() )
						//在第0单元存入状态个数，后面为状态
					{
					//	int statesTable[50];
					//	string str=",1,,2,34,,56,,";
						int n=1,mh=0,mt=0;
						while ( (mt=strTemp.find(',',mh)) >= 0 )
						{
					//		cout<<strTemp.substr(mh,mt-mh) ;
							string strState=strTemp.substr(mh,mt-mh);
							mh=mt+1;
							if ( strState.length() <= 0 ) 
							{
								continue;
							}
							statesTable[ iLine ][ iColumn ][n]=atoi( strState.c_str() );
							n++;
							if ( n>= STATES )
							{
								strError+=" The number of states exceeds !";
								return false;
							}
						}
						mt=strTemp.length();
						string strState=strTemp.substr(mh,mt-mh);
						//mh=mt+1;
						if ( strState.length() > 0 ) 
						{
							statesTable[ iLine ][ iColumn ][n]=atoi( strState.c_str() );
						}
						else
							n--;
						statesTable[ iLine ][ iColumn ][0]=n;
						strTemp="";
					}
						break;
				}
				if ( chr >='0' && chr<='9' || chr==',') 
				{
					strTemp += chrsTemp[j];
				}
				else	//处理strTemp并清空之
				{
					if(chr == '*' && iColumn == 0 )
					{
						statesTable[ iLine ][ iColumn ][ 0 ]= '*';
					}
					else
					{
						if( !strTemp.empty() )
						{
							int n=1,mh=0,mt=0;
							while ( (mt=strTemp.find(',',mh)) >= 0 )
							{
								cout<<strTemp.substr(mh,mt-mh) ;
								string strState=strTemp.substr(mh,mt-mh);
								mh=mt+1;
								if ( strState.length() <= 0 ) 
								{
									continue;
								}
								statesTable[ iLine ][ iColumn ][n]=atoi( strState.c_str() );
								n++;
							}
							mt=strTemp.length();
							string strState=strTemp.substr(mh,mt-mh);
							//mh=mt+1;
							if ( strState.length() > 0 ) 
							{
								statesTable[ iLine ][ iColumn ][n]=atoi( strState.c_str() );
							}
							else
								n--;
							statesTable[ iLine ][ iColumn ][0]=n;
							strTemp="";
						}
					}
					iColumn++;
					str="";
				}
				if ( iColumn > columnTable )
				{
					strError +="Error! \r\n the statesTable has errors !";
					return false;
				}
			}
		}
	}		
	
	lineTable=iLine;

	//判断statesTable 中状态转移是否正确，转移的状态是否超出最大状态
	bool bFinal=false;
	for( int ln=1;ln<= lineTable; ln++)
	{
		for( int cn=1; cn< columnTable; cn++)
		{
			if( statesTable[ ln ][ cn ][ 0 ]> lineTable-1 && statesTable[ ln ][ cn ][ 0 ] !='~'  )
			{
				strError +="Error! \n The state in the statesTable is beyound the max state !";
//				AfxMessageBox(strError);
//				cout<<strError;
				return false;
			}
		}
		if ( statesTable[ ln ][ 0 ][ 0 ] =='*' )
		{
			bFinal=true;
		}
	}
	if ( !bFinal ) 
	{
		strError +="Error! \n There is no final state in the statesTable!";
//		cout<<strError;
//		AfxMessageBox("Error! \n There is no final state in the statesTable!");
		return false;
	}

	return true;
}

bool Autom::Init()
{
	for(int i=0;i<LINES;i++)
		for( int j=0;j<COLUMNS; j++)
			for(int k=0;k<STATES; k++)
			statesTable[ i ][ j ][ k ] ='~';
	return true;
}
bool Autom::search(char *chrs,int length,int startState )
{
	//检验参数有效性

	//判断是否到达接受状态
	if ( length < 1 || *chrs == 0 )
	{
		if ( statesTable[ startState+1 ][ 0 ][ 0 ] =='*' )	//到达接受状态
		{
			return true;
		}
		else
			return false;		//不能接受的
	}
	
	//找到该字符
	int i =1;
	for(; i<= columnTable;i++)
	{
		if ( *chrs == statesTable[0][ i ][ 0 ] ) 
		{
			break;			
		}
	}
	if ( i <=columnTable )
	{
		int stateTemp=statesTable[ startState +1][ i ][ 0 ];
		if ( stateTemp != '~' )
		{
			chrs++;
			bool bReturn=false;
			for(int iStates=1;iStates<=stateTemp ; iStates++)
			{
				char buff[10];
				itoa(statesTable[ startState +1][ i ][ iStates ] ,buff,10);
				strError += buff;
				if (statesTable[ statesTable[ startState +1][ i ][ iStates ]+1 ][ 0 ][ 0 ] =='*') //已经到达接受状态
				{
					itoa(length ,buff,10);
					strPosInfo+= buff;
					strError +=',';
				}
				strError +=',';
				bReturn |= search(chrs,length-1, statesTable[ startState +1][ i ][ iStates ] );
			}
			if ( bReturn ) 
			{
				return true;
			}
		}
		else
			return false;

		
	}
	else
		return false;

	return false;
}

bool Autom::Proc(const char *chrs, int length)
{
	char *strTemp=new char[ length ];
	memset( strTemp,0,length );
	strcpy( strTemp, chrs );
	strError="";

//	cout<<endl<<"strTemp: "<<strTemp<<endl;
	if (length > MAXLENGTH )
	{
//		cout<<"The length is too large !";
		strError +="The length is too large !";
		return false;
	}
	if( search(strTemp, length,0 ) )
	{
//		cout<<"Accept"<<endl;
		strError += "Accept";
		return true;
	}
	else
	{
		strError += "Unaccept" ;
//		cout<<"Unaccept"<<endl;
		return false;
	}
	delete strTemp;
}


string Autom::GetErrors()
{
	return strError;
}

//DEL string Autom::GetStatesTable()
//DEL {
//DEL 	string strTable;
//DEL 	for(int i=0; i<=lineTable; i++)
//DEL 	{
//DEL 		for(int j=0; j<=columnTable; j++)
//DEL 		{
//DEL 			if ( statesTable[i][j][ 0 ] <30 ) 
//DEL 			{
//DEL 				char buff[10];
//DEL 				itoa(statesTable[i][j][ 0 ],buff,10);
//DEL 				strTable += buff;
//DEL 			//	cout<<buff;
//DEL 			}
//DEL 			else
//DEL 			{
//DEL 				strTable += (char) statesTable[i][j] ;
//DEL 			//	cout<< (char) statesTable[i][j] ;
//DEL 			}
//DEL 			strTable +='\t';
//DEL 		}
//DEL 		strTable +="\r\n";
//DEL 	}
//DEL 	return strTable;
//DEL }

void Autom::Output(string fileName)
{	
	ofstream ou(fileName.c_str());
	for(int i=0;i<=lineTable;i++)
	{
		for( int j=0;j<=columnTable; j++)
		{
			if (statesTable[ i ][ j ][ 0 ] < 20)
			{
				int k=1;
				for(;k<statesTable[ i ][ j ][ 0 ]; k++)
					ou<<statesTable[ i ][ j ][ k ]<<',';
				ou<<statesTable[ i ][ j ][ k ]<<'\t';
			}
			else
				ou<<(char)statesTable[ i ][ j ][ 0 ]<<'\t' ;		
		}
		ou<<endl;
	}
}

string Autom::OutputTableStr()
{
	string tableStr;
	for(int i=0;i<=lineTable;i++)
	{
		for( int j=0;j<=columnTable; j++)
		{
			if (statesTable[ i ][ j ][ 0 ] < 20)
			{
				int k=1;char buff[10];
				for(;k<statesTable[ i ][ j ][ 0 ]; k++)
				{					
					tableStr+=itoa( statesTable[ i ][ j ][ k ] ,buff,10 );
				//	tableStr+=buff;
					tableStr+=',';
				}
				tableStr+=itoa( statesTable[ i ][ j ][ k ],buff,10 );
				tableStr+='\t';
			}
			else
			{
				tableStr+=(char)statesTable[ i ][ j ][ 0 ];
				tableStr+='\t' ;		
			}
		}
		tableStr+='\n';

	}
	return tableStr;
}

int Autom::GetValue(int i, int j, int k)
{
	if ( i< LINES && j< COLUMNS && k< STATES )
	{
		return statesTable[i][j][k];
	}
	return -1;
}

bool Autom::CreateGraphic()
{
	for( int i=0;i< STATES; i++)
	{
		for( int j=0; j< STATES; j++)
		{
			statesGraphic[i][j] = '~';
		}
	}

	for( int s=1; s<= lineTable ; s++)
	{
		if ( statesTable[s][0][0] == '*')
		{
			statesGraphic[ s ][0] = '*';
			statesGraphic[0][ s ] = '*';
		}
		for( int c=1; c<= columnTable; c++)
		{
			if ( statesTable[s][c][0] != '~' )
			{
				for( int k=1;k<=statesTable[s][c][0]; k++)
				{
					statesGraphic[s][ statesTable[s][c][k]+1] = statesTable[0][c][0];
				}
			}
		}
	}
/*
	ofstream ou("graphic.txt");
	for(int i0=0;i0<=lineTable;i0++)
	{
		for( int j=0;j<=lineTable; j++)
		{
			ou<<(char)statesGraphic[ i0 ][ j ] <<'\t';		
		}
		ou<<endl;
	}
*/
	return true;
}

int Autom::GetGraphic(int i,int j)
{
	if ( i< STATES && j< STATES ) 
	{
		return statesGraphic[i][j];
	}
	return -1;
}

int Autom::GetLine()
{
	return lineTable;
}

int Autom::GetColumn()
{	
	return columnTable;
}


bool Autom::InitFromRE(string strRE)
{
//由正则表达式创建epzilon-NFA

//计算epzilon闭包，构造NFA

	return true;
}

string Autom::GetPosInfo()
{
	return strPosInfo;
}