p6.cpp

扫描样本字符串

#include "stdafx.h"

#include <iostream>
#include <math.h>
#include <list>
#include <stack>
#include <queue>
#include <afx.h>
//#include <stdio.h>

using   namespace   std;
  
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的数据结构*/


/*DFA数据结构*/
typedef list<State> STATE_LIST;//状态集

typedef struct
{
	STATE_LIST statelist;
	Symbol symbol;
}StateListNode;//状态集节点

typedef list<StateListNode> STATELISTNODE_LIST;//状态集节点列表

typedef struct
{
	STATE_LIST dstate;
	STATELISTNODE_LIST slnList;
}TransListNode;//保存一个状态集经过所有元字符所到达的状态集

typedef list<TransListNode> TRANS_LIST;//DFA转换表
//DFA数据结构


CString rExp;//正则表达式
NODE_LIST* NFA_List;//保存NFA图
NFA_LIST NFAlist;
LETTER_LIST letterlist;//保存NFA字母表

NFA objNFA;//保存NFA的初始状态和终止状态
int StateSum;//记录NFA的总状态数 


STATE_LIST* DFAStateArray=NULL;//DFA状态集查询表
NODE_LIST* DFAtransArray=NULL;//DFA状态转换表
int DFAStateNum;//DFA状态总数
STATE_LIST startlist;//DFA开始状态集
STATE_LIST acceptlist;//DFA接受状态集

/*
//对外接口函数
bool BuildNFA(CString& r);//创建NFA
void BuildDFA();//创建DFA
void MinDFA();//最小化DFA

//void ClearNFA();//清空数据结构里保存的东西
void ClearDFA();//清空数据结构里保存的东西
void ClearMinDFA();//清空数据结构里保存的东西*/

//////////////////// NFA Function realization/////////////////
/*以下是正则表达式到NFA的几个函数*/
void Translate(CString& r);//转换正则表达式
void GetLetters(CString& r);//获取字母表
void RToNFA(CString& r,NFA_LIST& NFAlist);//正则表达式到NFA
void TranslateNFA(NFA_LIST& NFAlist);//改变NFA的存储结构

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

}


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]!='('&&r[i]!='|')
			//满足此条件的字母后面加'&'
		{
//			if(r[i+1]=='a'&&r[i+1]=='b'||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(NFA_LIST& NFAlist,NFA& val1,NFA& val2)//连接操作,返回新状态的NFA
{
	
	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);

			break;
		}
	}
	
	val.start=val1.start;//以左操作数的开始状态为初始状态为新NFA的开始状态
	val.end=val2.end;//以右操作数的开始状态为接受状态为新NFA的接受状态
	
	return val;
}

NFA AddOr(NFA_LIST& NFAlist,NFA& val1,NFA& val2,State& StateNum)//选择操作,返回新状态的NFA
{
	
	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);

    val.start=StateNum++;//新建两个新的状态
	val.end=StateNum++;
	
	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);			
			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);			
			break;
		}
	}
	nodelist1.clear();//清空链表,释放内存空间
	return val;
}

NFA AddRepeat(NFA_LIST& NFAlist,NFA& val1,State& StateNum)//闭包操作,返回新状态的NFA
{
    NFA val;
	int i;
	Node node;
	NODE_LIST nodelist1,nodelist2;
	NFA_LIST::iterator iter;

    val.start=StateNum++;//新建两个新的状态
	val.end=StateNum++;

	node.state=val1.start;
	node.symbol='\0';//添加一条空字符的转换边
	nodelist1.push_back(node);

	node.state=val.end;
	node.symbol='\0';//添加一条空字符的转换边
	nodelist1.push_back(node);

    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);
 			
			node.state=val.end;
			node.symbol='\0';//添加一条空字符的转换边
			iter->push_back(node);
	
			break;
		}
	}
    nodelist1.clear();//清空链表,释放内存空间
	return val;
}


void TranslateNFA(NFA_LIST& NFAlist)//改变NFA的存储结构
{
	int i;
	NFA_LIST::iterator iter;
	NODE_LIST::iterator iter1;
	StateSum=NFAlist.size();
    NFA_List=new NODE_LIST[StateSum];
    for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)
	{
		for(iter1=iter->begin();iter1!=iter->end();iter1++)
			NFA_List[i].push_back(*iter1);
	}
}

void RToNFA(CString& r,NFA_LIST& NFAlist)//正则表达式到NFA
{
	list<NFA> l1;//NFA栈,NFA保存的是一个NFA的开始状态和终止状态
	list<Symbol> l2;//符号栈,用于保存正则表达式运算符
	int i=0;//标志当前字符在正则表达式字符串中的位置
	char ch;//暂存出栈字符
    NFA val1,val2,val;//保存NFA运算操作数和结果
	State StateNum=0;//当前状态数
	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;
		
		
			val.start=StateNum++;//新建两个新的状态

			node.state=val.end=StateNum++;
			node.symbol=r[i];
            l1.push_back(val);//nfa进栈

		
			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(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(NFAlist,val1,val2,StateNum);//运算
					l1.push_back(val);//结果放回NFA栈
					break;
				case '*':
					val1=l1.back();//闭包运算只取一个操作数val1
					l1.pop_back();
					val=AddRepeat(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(NFAlist,val1,StateNum);
						l1.push_back(val);
						break;
					case '&':
						val2=l1.back();
						l1.pop_back();
						val1=l1.back();
						l1.pop_back();
						val=AddAnd(NFAlist,val1,val2);
						l1.push_back(val);
						break;
					case '|':
						val2=l1.back();
						l1.pop_back();
						val1=l1.back();
						l1.pop_back();
						val=AddOr(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(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(NFAlist,val1,val2);