//nfa2dfa.cpp
#include <iostream>
#include <string>
using namespace std;
const int Max=20;
typedef struct ArcNode{
int adjvex;//该弧所指向的顶点的位置
char info; //权
struct ArcNode *nextarc;//指向下一条弧的指针
}ArcNode;
typedef struct VNode{
char data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode;
class Nfa
{
public:
Nfa(); //构造函数,初始化nfa
int FindAdj(char c); //返回c状态的在邻接表中的序号
void AlpAdd(char c); //向字母表集合中添加表中没有的新元素c
void InitVisit(); //初始化Visited集合
void e_closure(int index); //求单一状态c的e-闭包
void e_closure(int a[]); //重载的状态集合的e-闭包
void move(int I,char a); //单一状态I的a弧转换
void move(int I[],char a); //重载的状态集合的a弧转换
void Nfa::Visit_I(int *Temp);
//Visited转换为集合
void Insert(int I[],int a); //向状态集合中添加新元素
int TAdd(int I[]); //状态矩阵T中加入新状态集合
void Resault(int i);
void Nfa_Dfa();
private:
int K; //状态数
int T[Max][Max]; //状态子集矩阵
VNode AdjList[Max]; //nfa,邻接表的数据结构存储
VNode Dfa[Max]; //dfa
bool Visited[Max]; //存e-闭包结果
char Alp[Max]; //字母表,0号单元用于存放个数
};
Nfa::Nfa()
{
K=Alp[0]=0;
char c;
string line;
ArcNode *p;
while(cin>>c&&c!='#')
{
AdjList[K].data=c;
AdjList[K].firstarc=new ArcNode;
AdjList[K].firstarc->nextarc=NULL;
K++;
}
getline(cin,line);
while(getline(cin,line)&&line!="#")
{
int index=FindAdj(line[0]);
if(index!=-1)
{
p=AdjList[index].firstarc;
while(p->nextarc)
p=p->nextarc;
p->nextarc=new ArcNode;
p->nextarc->nextarc=NULL;
p->nextarc->adjvex=FindAdj(line[4]);
p->nextarc->info=line[2];
AlpAdd(p->nextarc->info);
}
}
cout<<"------------------------------"<<endl;
cout<<"Initialization completely."<<endl;
cout<<"K={";
for(int i=0;i<K-1;i++)
cout<<AdjList[i].data<<",";
cout<<AdjList[K-1].data<<"}."<<endl;
cout<<"∑={";
for(int i=1;i<(int)Alp[0];i++)
cout<<Alp[i]<<",";
cout<<Alp[Alp[0]]<<"}."<<endl;
for(int i=0;i<K;i++)
{
p=AdjList[i].firstarc;
p=p->nextarc;
while(p)
{
cout<<"f("<<AdjList[i].data<<","<<p->info<<")="<<p->adjvex<<" ";
p=p->nextarc;
}
if(i<K&&AdjList[i].firstarc->nextarc)
cout<<endl;
}
cout<<"------------------------------"<<endl;
for(int i=0;i<Max;i++)
T[i][0]=0;
}
int Nfa::FindAdj(char c)
{
for(int i=0;i<K;i++)
if(c==AdjList[i].data)
return i; //返回序号
return -1; //没有查找到则返回-1
}
void Nfa::AlpAdd(char c)
{
if(c=='*') return;
for(int i=1;i<=(int)Alp[0];i++)
if(c==Alp[i])
return; //集合中已含有
Alp[++Alp[0]]=c;
}
void Nfa::e_closure(int index)
{
ArcNode *p;
Visited[index]=true;
p=AdjList[index].firstarc->nextarc;
while(p)
{
if(!Visited[p->adjvex]&&p->info=='.')
e_closure(p->adjvex);
p=p->nextarc;
}
}
void Nfa::e_closure(int a[])
{
InitVisit();
for(int i=1;i<=a[0];i++)
e_closure(a[i]);
}
void Nfa::InitVisit()
{
for(int i=0;i<K;i++)
Visited[i]=false;
}
void Nfa::move(int I,char a)
{
ArcNode *p;
p=AdjList[I].firstarc->nextarc;
while(p)
{
if(p->info==a)
Visited[p->adjvex]=true;
p=p->nextarc;
}
}
void Nfa::move(int I[],char a)
{
InitVisit();
for(int i=1;i<=I[0];i++)
move(I[i],a);
}
void Nfa::Insert(int I[],int index)
{
//I[0]表示元素个数;
int flag=0;
for(int i=1;i<=I[0];i++)
{
if(index==I[i]) //状态集合中已有index状态
return;
else if(index>I[i])
flag=i; //标记待插入位置
}
I[0]++;flag++;
for(int i=I[0];i>flag;i--)
I[i]=I[i-1];
I[flag]=index;
}
int Nfa::TAdd(int I[])
{//T[0][0]当前集合的个数
int i=1;
for(;i<=T[0][0];i++)
{
if(I[0]==T[i][0])
{ int j=1;
for(;j<=I[0];j++)
if(I[j]!=T[i][j])
break;
if(j==(I[0]+1)) //说明矩阵T中已有I集合,并返回位置
return i;
}
}
T[0][0]++;
for(i=0;i<=I[0];i++)
T[T[0][0]][i]=I[i];
return -1; //说明矩阵T中没有I集合,插入并返回-1
}
void Nfa::Visit_I(int *Temp)
{
Temp[0]=0;
for(int i=0;i<K;i++)
if(Visited[i])
Temp[++Temp[0]]=i;
}
void Nfa::Resault(int i)
{
int j,k;
ArcNode *p;
cout<<"Nfa To Dfa:"<<endl;
for(j=0;j<i;j++)
{
cout<<(int)Dfa[j].data<<"={";
for(k=1;k<T[j+1][0];k++)
cout<<AdjList[T[j+1][k]].data<<",";
cout<<AdjList[T[j+1][k]].data<<"}/t/t";
if((j+1)%2==0)
cout<<endl;
}
if((j+1)%2==0) cout<<endl;
cout<<endl;
cout<<"S={";
for(int j=0;j<i-1;j++)
cout<<(int)Dfa[j].data<<",";
cout<<(int)Dfa[i-1].data<<"}."<<endl;
cout<<"∑={";
for(int j=1;j<(int)Alp[0];j++)
cout<<Alp[j]<<",";
cout<<Alp[Alp[0]]<<"}."<<endl;
for(int j=0;j<i;j++)
{
p=Dfa[j].firstarc;
p=p->nextarc;
while(p)
{
cout<<"D("<<(int)Dfa[j].data<<","<<p->info<<")="<<p->adjvex<<" ";
p=p->nextarc;
}
if(j<i&&Dfa[j].firstarc->nextarc)
cout<<endl;
}
cout<<"Finished."<<endl;
cout<<"------------------------------"<<endl;
}
void Nfa::Nfa_Dfa()
{
int Temp[Max],i=0,j=1;
ArcNode *p;
InitVisit();
e_closure(0); //选择第一个状态K0
Visit_I(Temp);
TAdd(Temp);//Dfa中加入第一个状态
i++;j++; //将选择的第一个状态的e-闭包加入C矩阵中//并标记
while(i!=j)
{
Dfa[i-1].data=i-1;
Dfa[i-1].firstarc=new ArcNode;
Dfa[i-1].firstarc->nextarc=NULL;
for(int ii=1;ii<=Alp[0];ii++)
{
for(int jj=0;jj<=T[i][0];jj++)
Temp[jj]=T[i][jj];
move(Temp,Alp[ii]);
Visit_I(Temp);
if(Temp[0])
{
e_closure(Temp);
Visit_I(Temp);
int flag=TAdd(Temp);
if(flag==-1)
{
j++;
p=Dfa[i-1].firstarc;
while(p->nextarc)
{p=p->nextarc;}
p->nextarc=new ArcNode;
p->nextarc->adjvex=T[0][0]-1;
p->nextarc->info=Alp[ii];
p->nextarc->nextarc=NULL;
}
else
{
p=Dfa[i-1].firstarc;
while(p->nextarc)
{p=p->nextarc;}
p->nextarc=new ArcNode;
p->nextarc->adjvex=flag-1;
p->nextarc->info=Alp[ii];
p->nextarc->nextarc=NULL;
}
}
}
i++;
}
Resault(i-1);
}
int main()
{
Nfa nfa;
nfa.Nfa_Dfa();
getchar();
return 0;
}
评论0