nfa.cpp

扫描样本字符串

#include "Globals.h"
#include "stdafx.h"
#include "afx.h"

typedef int State;//定义状态的类型
typedef char Symbol;//定义元字符类型

typedef struct
{
	State start;
	State end;
}NFA;//定义NFA始态和终态

typedef struct
{
	State state;
	Symbol symbol;
}Node;//NFA邻接表元素类型

typedef struct
{
	State start;
	State end;
	Symbol symbol;
}ARC;//边

/*
/*NFA的数据结构
typedef list<Node> NODE_LIST;//节点链表
typedef list<NODE_LIST> NFA_LIST;//NFA列表
typedef list<char> LETTER_LIST;//字母表
/*NFA的数据结构*/


//正则表达式
CString rExp;
LETTER_LIST letterlist;
NFA objNFA;
NODE_LIST* NFA_List=NULL;


/*

//NFA_LIST* NFAlist=NULL;


int StateSum;//状态总数

void Translate(CString& r);//转换正则表达式
void GetLetters(CString& r);//获取字母表
void RToNFA(CString& r,NFA_LIST& NFAlist);//正则表达式到NFA
void TranslateNFA(NFA_LIST& NFAlist);

/*
void ClearNFA()//清空数据结构里保存的东西
{
	letterlist.clear();
	if(NFA_List!=NULL)
	{
    delete []NFA_List;
		NFA_List=NULL;
	}
}

bool BuildNFA(CString& r)//创建NFA
{
	

	NFA_LIST NFAlist;

	Translate(r);
	GetLetters(r);
	RToNFA(r,NFAlist);
	TranslateNFA(NFAlist);

	NFAlist.clear();
	return true;
}

/*

void Translate(CString& r)//转换正则表达式,主要把连接符号以'&'标识出来
{
	list<char> chList;
	int i=0;
	r+='\0';
	int n=r.GetLength();

    while(i<n-1)//以链表把转换后的正则表达式保存起来
	{
		chList.push_back(r[i]);
//		if(r[i]>='a'&&r[i]<='z'||r[i]>='A'&&r[i]<='Z'||r[i]==')'||r[i]=='*')
		if(r[i]!='('&&r[i]!='|')
			//满足此条件的字母后面加'&'
		{
//			if(r[i+1]>='a'&&r[i+1]<='z'||r[i+1]>='A'&&r[i+1]<='Z'||r[i+1]=='(')
			if(r[i+1]!=')'&&r[i+1]!='*'&&r[i+1]!='|'&&r[i+1]!='\0')
				chList.push_back('&');
		}
		i++;
	}
	r.Empty();
	list<char>::iterator iter;
	for(iter=chList.begin();iter!=chList.end();iter++)
	{
		r+=*iter;
	}
	chList.clear();//清空链表,释放内存空间
}

void GetLetters(CString& r)
{
	int i=0;
	char letter[128];
	memset(letter,0,128);
	int n=r.GetLength();
	while(i<n)
	{
		if(r[i]!='&'&&r[i]!='|'&&r[i]!='*'&&r[i]!='('&&r[i]!=')')
		{
			//letterlist.push_back(r[i]);
			letter[i]=r[i];
		}
		i++;
	}
	for(i=0;i<128;i++)
	{
		if(letter[i]!=0)
		{
			letterlist.push_back((char)letter[i]);
		}
	}
}


NFA AddAnd(CNODE_LIST &cnodelist,STATE_STACK &statestack,NFA_LIST& NFAlist,NFA& val1,NFA& val2)//连接操作,返回新状态的NFA
{
	ARC tem;
	NFA val;
	int i;
	NFA_LIST::iterator iter;


	for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)//寻找第val1.end个节点
	{
		if(i==val1.end)//向此节点的相邻节点链表加入一个节点
		{
			Node node;
			node.state=val2.start;
			node.symbol='\0';
			iter->push_back(node);
			
            operations.push_back(2);
			tem.symbol='\0';
			tem.start=val1.end;
			tem.end=val2.start;
			arcs.push_back(tem);
			
			break;
		}
	}
	
	val.start=val1.start;//以左操作数的开始状态为初始状态为新NFA的开始状态
	val.end=val2.end;//以右操作数的开始状态为接受状态为新NFA的接受状态
	
	return val;
}

NFA AddOr(CNODE_LIST &cnodelist,STATE_STACK &statestack,NFA_LIST& NFAlist,NFA& val1,NFA& val2,State& StateNum)//选择操作,返回新状态的NFA
{
	ARC tem;
	NFA val;
	int i;
	NODE_LIST nodelist1,nodelist2;
	Node node;
	NFA_LIST::iterator iter;

	
	node.state=val1.start;
	node.symbol='\0';//添加一条空字符的转换边
	nodelist1.push_back(node);
	
	node.state=val2.start;
	node.symbol='\0';//添加一条空字符的转换边
	nodelist1.push_back(node);
	NFAlist.push_back(nodelist1);//向邻接表加入两个新的链表
	NFAlist.push_back(nodelist2);
	
	operations.push_back(1);
	drawstates.push_back(StateNum);
    val.start=StateNum++;//新建两个新的状态
	operations.push_back(1);
	drawstates.push_back(StateNum);
	val.end=StateNum++;


	///////////////////////////////////////
	statechain1=statestack.back();
	statestack.pop_back();//取状态链表栈中的最顶不的链表
	statechain2=statestack.back();
	statestack.pop_back();
	X_ADD(cnodelist,statechain1,xadd);
	X_ADD(cnodelist,statechain2,xadd);
	Y_ADD(cnodelist,statechain1,yadd);
	Y_ADD(cnodelist,statechain2,-yadd);


	statechain.push_back(val.start);//合并经过运算的状态链表
	for(iter1=statechain1.begin();iter1!=statechain1.end();iter1++)
	{
		statechain.push_back(*iter1);
	}
	for(iter1=statechain2.begin();iter1!=statechain2.end();iter1++)
	{
		statechain.push_back(*iter1);
	}
	statechain.push_back(val.end);
	statestack.push_back(statechain);
	state1=statechain1.back();
	state2=statechain2.back();

	cnode.x=startx;
	cnode.y=starty;
	cnodelist.push_back(cnode);//添加一个该状态的结点，定义在这个链表的开头
	cnode.x=max_(FIND(cnodelist,state1).x,FIND(cnodelist,state2).x)+xadd;
	cnode.y=(FIND(cnodelist,state1).y+FIND(cnodelist,state2).y)/2;
	cnodelist.push_back(cnode);
	statechain.clear();
	statechain1.clear();
	statechain2.clear();
	///////////////////////////////////////////////////////////

	
	operations.push_back(2);
	tem.symbol='\0';
	tem.start=val.start;
	tem.end=val1.start;
	arcs.push_back(tem);
	
	operations.push_back(2);
	tem.symbol='\0';
	tem.start=val.start;
	tem.end=val2.start;
	arcs.push_back(tem);
	
	
	for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)
	{
		if(i==val1.end)//向此节点的相邻节点链表加入一个节点
		{
			Node node;
			node.state=val.end;
			node.symbol='\0';//添加一条空字符的转换边
			iter->push_back(node);
			
			operations.push_back(2);
			tem.symbol='\0';
			tem.start=val1.end;
			tem.end=val.end;
			arcs.push_back(tem);
			
			break;
		}
	}
	
	for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)
	{
		if(i==val2.end)//向此节点的相邻节点链表加入一个节点
		{
			Node node;
			node.state=val.end;
			node.symbol='\0';//添加一条空字符的转换边
			iter->push_back(node);
			
            operations.push_back(2);
			tem.symbol='\0';
			tem.start=val2.end;
			tem.end=val.end;
			arcs.push_back(tem);
			
			break;
		}
	}
	nodelist1.clear();//清空链表,释放内存空间
	return val;
}

NFA AddRepeat(CNODE_LIST &cnodelist,STATE_STACK &statestack,NFA_LIST& NFAlist,NFA& val1,State& StateNum)//闭包操作,返回新状态的NFA
{
  NFA val;
	int i;
	Node node;
	NODE_LIST nodelist1,nodelist2;
	NFA_LIST::iterator iter;
	ARC tem;
	
	operations.push_back(1);
	drawstates.push_back(StateNum);
  val.start=StateNum++;//新建两个新的状态
	operations.push_back(1);
	drawstates.push_back(StateNum);
	val.end=StateNum++;

	node.state=val1.start;
	node.symbol='\0';//添加一条空字符的转换边
	nodelist1.push_back(node);
	operations.push_back(2);
	tem.symbol='\0';
	tem.start=val.start;
	tem.end=val1.start;
	arcs.push_back(tem);
	
	node.state=val.end;
	node.symbol='\0';//添加一条空字符的转换边
	nodelist1.push_back(node);
	operations.push_back(3);
	tem.symbol='\0';
	tem.start=val.start;
	tem.end=val.end;
	arcs.push_back(tem);
	
  NFAlist.push_back(nodelist1);//向邻接表加入两个新的链表
	NFAlist.push_back(nodelist2);
	
	for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)
	{
		if(i==val1.end)
		{
			Node node;
			node.state=val1.start;
			node.symbol='\0';//添加一条空字符的转换边
			iter->push_back(node);
            
			operations.push_back(3);//添加一个操作,1.为节点生成操作2.为直线边3.为曲线边
			tem.symbol='\0';
			tem.start=val1.end;
			tem.end=val1.start;
			arcs.push_back(tem);
			
			node.state=val.end;
			node.symbol='\0';//添加一条空字符的转换边
			iter->push_back(node);
			
			operations.push_back(2);//添加一个操作,1.为节点生成操作2.为直线边3.为曲线边
			tem.symbol='\0';
			tem.start=val1.end;
			tem.end=val.end;
			arcs.push_back(tem);
			break;
		}
	}
    nodelist1.clear();//清空链表,释放内存空间
	return val;
}

void RToNFA(CString& r,NFA_LIST& NFAlist,CNODE_LIST &cnodelist,STATE_STACK &statestack)//正则表达式到NFA
{
	list<NFA> l1;//NFA栈,NFA保存的是一个NFA的开始状态和终止状态
	list<Symbol> l2;//符号栈,用于保存正则表达式运算符
	int i=0;//标志当前字符在正则表达式字符串中的位置
	char ch;//暂存出栈字符
    NFA val1,val2,val;//保存NFA运算操作数和结果
	State StateNum=0;//当前状态数
	ARC tem;
	int n=r.GetLength();
	
	while(i<n)//如果正则表达式还没结束,do
	{
//		if(r[i]>='a'&&r[i]<='z'||r[i]>='A'&&r[i]<='Z')//遇到正则表达式
		if(r[i]!='('&&r[i]!=')'&&r[i]!='*'&&r[i]!='|'&&r[i]!='&')
		{
			NODE_LIST nodelist1;
			NODE_LIST nodelist2;

		//	NFA nfa;
			Node node;
			operations.push_back(1);//添加一个操作,1.为节点生成操作2.为直线边3.为曲线边
			drawstates.push_back(StateNum);
			val.start=StateNum++;//新建两个新的状态
			operations.push_back(1);//添加一个操作,1.为节点生成操作2.为直线边3.为曲线边
			drawstates.push_back(StateNum);
			node.state=val.end=StateNum++;
			node.symbol=r[i];
            l1.push_back(val);//nfa进栈

			tem.symbol=r[i];
			tem.start=val.start;
			tem.end=val.end;
			arcs.push_back(tem);
			operations.push_back(2);
			
			
			nodelist1.push_back(node);//加入一条人r[i]字符的转换边
			NFAlist.push_back(nodelist1);//向邻接表加入两个新的链表
			NFAlist.push_back(nodelist2);
			nodelist1.clear();//清空链表,释放内存空间
		}
		else if(r[i]=='(')//遇到'(',暂存,以待后来作为一个括号运算完的判断
		{
			l2.push_back(r[i]);
		}
		else if(r[i]==')')//遇到'(',舍弃,运算括号内的表达式
		{
			ch=l2.back();
			l2.pop_back();
			while(ch!='(')//如果括号内的表达式还没运算完,do
			{
				switch(ch)
				{
				case '&'://连接操作
					val2=l1.back();//取操作数val2
					l1.pop_back();
					val1=l1.back();//取操作数val1
					l1.pop_back();
					val=AddAnd(cnodelist,statestack,NFAlist,val1,val2);//运算
					l1.push_back(val);//结果放回NFA栈
					break;
				case '|':
					val2=l1.back();//取操作数val2
					l1.pop_back();
					val1=l1.back();//取操作数val1
					l1.pop_back();
					val=AddOr(cnodelist,statestack,NFAlist,val1,val2,StateNum);//运算
					l1.push_back(val);//结果放回NFA栈
					break;
				case '*':
					val1=l1.back();//闭包运算只取一个操作数val1
					l1.pop_back();
					val=AddRepeat(cnodelist,statestack,NFAlist,val1,StateNum);//运算
					l1.push_back(val);//结果放回NFA栈
					break;
				}
				ch=l2.back();//取出下一运算符
				l2.pop_back();
			}
		}
		else if(r[i]=='|')//遇到'|'
		{
			if(!l2.empty())
			{
				ch=l2.back();
				while(ch!='(')//向左运算级高,先运算左边的表达式
				{
					ch=l2.back();
					l2.pop_back();
					switch(ch)
					{
					case '*':
						val1=l1.back();
						l1.pop_back();
						val=AddRepeat(cnodelist,statestack,NFAlist,val1,StateNum);
						l1.push_back(val);
						break;
					case '&':
						val2=l1.back();
						l1.pop_back();
						val1=l1.back();
						l1.pop_back();
						val=AddAnd(cnodelist,statestack,NFAlist,val1,val2);
						l1.push_back(val);
						break;
					case '|':
						val2=l1.back();
						l1.pop_back();
						val1=l1.back();
						l1.pop_back();
						val=AddOr(cnodelist,statestack,NFAlist,val1,val2,StateNum);
						l1.push_back(val);
						break;
					}
					if(!l2.empty())
						ch=l2.back();
					else
						break;
				}//while
			}//if
			l2.push_back(r[i]);//保存操作符
		}
		else if(r[i]=='&')//遇到'&'
		{
			if(!l2.empty())
			{
				ch=l2.back();
				switch(ch)//向左运算级高,先运算左边的表达式
				{
				case '*':
					ch=l2.back();
					l2.pop_back();
					val1=l1.back();
					l1.pop_back();
					val=AddRepeat(cnodelist,statestack,NFAlist,val1,StateNum);
					l1.push_back(val);
					break;
				case '&':
					ch=l2.back();
					l2.pop_back();
					val2=l1.back();
					l1.pop_back();
					val1=l1.back();
					l1.pop_back();
					val=AddAnd(cnodelist,statestack,NFAlist,val1,val2);
					l1.push_back(val);
					break;
				}
			}//if
			l2.push_back(r[i]);//保存操作符
		}
		else if(r[i]=='*')//遇到'*'
		{
			if(!l2.empty())
			{
				ch=l2.back();
				switch(ch)//向左运算级高,先运算左边的表达式
				{
				case '*':
					ch=l2.back();
					l2.pop_back();
					val1=l1.back();
					l1.pop_back();
					val=AddRepeat(cnodelist,statestack,NFAlist,val1,StateNum);
					l1.push_back(val);
					break;
				}
			}//if
			l2.push_back(r[i]);//保存操作符
		}//else if
		i++;
	}//while
	while(!l2.empty())//剩余在'()'外的表达式的运算
	{
		ch=l2.back();
		l2.pop_back();
		switch(ch)
		{
		case '*':
			val1=l1.back();
			l1.pop_back();
			val=AddRepeat(cnodelist,statestack,NFAlist,val1,StateNum);
			l1.push_back(val);
			break;
		case '&':
			val2=l1.back();
			l1.pop_back();
			val1=l1.back();
			l1.pop_back();
			val=AddAnd(cnodelist,statestack,NFAlist,val1,val2);
			l1.push_back(val);
			break;
		case '|':
			val2=l1.back();
			l1.pop_back();
			val1=l1.back();
			l1.pop_back();
			val=AddOr(cnodelist,statestack,NFAlist,val1,val2,StateNum);
			l1.push_back(val);
			break;
		}
	}
	objNFA=val;//保存最终的NFA的始态和终态
}

*/