#include <fstream>
#include <iostream>
#include <memory>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <set>
using namespace std;
/*
从NFA -> DFA
步骤:
1.将所有还未计算的集合计算完(初始时,讲开始点s所在集合 设为未计算集合)
2.对于每个未计算的集合计算 每条边 (a,b) ,如果产生一个新的完全不同的set,就把他加入集合中。
3.如何计算一个新产生的set呢? 按照e边扩展。
!!子集构造法按照书的P26, 用栈来实现,队列其实也行,深搜也行
e-closure (e的闭包) 计算按书上方法栈, floodfill 方法也行
*/
typedef set<int> SI;
typedef vector<int> VI;
typedef pair<SI::iterator , bool > PI;
const int N = 10000;
VI g[N][300];//g[i][j] 表示对于点 i 经过符号 j 到达的点,有向
int n=0,m=0;//点数,边的种类数
int e_edge=-1;//记录e边的编号
char edge[300];//每个 边的编号 对应的字符
int original[N];//对应的原编号
int v[300];//存 某个字符是否用过, 用过的话,就是它对应的标记号
int v2[N];//存 某个数字是否用过,用过的话,就是它对应的标记号
int start;
VI end;
//以下为保存DFA结果
int rg[N][300];
SI rset[N];
int n2;//n2 集合数 ;边的种类数 应该保持不变,除了e边
int begin2=0;//起始和结束集合
VI end2;
void debug_show_set( SI &s)
{
for ( SI::iterator si = s.begin(); si!=s.end();si++ )
cout<<*si<<" ";
}
void inputing() //读入边,转化为矩阵
{
int i,a,b,r;
char ch;
memset(v,-1,sizeof(v));
memset(v2,-1,sizeof(v2));
cout<<"边的数目:";cin>>r;
for (i=0;i<r;i++)
{
cin>>a>>ch>>b;
if (-1==v2[ a ])
{
original[ n ] = a;
v2[a] = n++;
}
a = v2[a];
if (-1==v2[ b ])
{
original[ n ]= b;
v2[b] = n++;
}
b = v2[b];
if ( -1==v[ ch ] )
{
edge[m] = ch;
v[ch] = m++;
}
if (ch == 'e')
e_edge = v[ch];
ch = v[ch];
g[ a ][(int)ch].push_back(b);
}
cout<<"e_edge is "<<e_edge<<endl;//debug
cout<<"起点";cin>>start;
start = v2[start];
cout<<"终点数目 及各终点";cin>>a;
for (i=0;i<a;i++)
{
cin>>b;
b = v2[b];
end.push_back( b );
}
}
SI e_closure( SI & s)// 求 s 的 e的闭包 栈 方法
{
SI r = s;
SI::iterator si;
int stack[N],top=0;
memset(stack,0,sizeof(stack));
for (si = s.begin();si!=s.end();si++)
{
stack[top++] = *si;
}
//begin stack
while (top)
{
top--;
int i,j;
j = stack[top];
PI p1;//pair类型, 第二个参数是bool
for (i=0;i<g[ j ][ e_edge ].size();i++ )
{
p1 = r.insert( g[ j ][ e_edge ][ i ] );
if (p1.second == true)
{
stack[top++] = g[ j ][ e_edge ][i];
}
}
}
return r;
}
SI move( SI & s,int j )//用 j 编号的边走一步
{
SI r;
SI :: iterator si;
for (si = s.begin();si!=s.end();si++)
for (int i=0;i<g[ *si ][ j ].size();i++ )
{
int temp;
temp = g[*si][j][i];
r.insert( temp );
}
return r;
}
bool contain_end(const SI & s)
{
int i;
for (i=0;i<end.size();i++)
if ( s.find( end[ i ] ) != s.end() )
return 1;
return 0;
}
void find_sub_set()
{
int stack[N],top;
memset(stack,0,sizeof(stack));
top = 0;
SI temp;
temp.insert(start);
rset[ n2++ ] = e_closure( temp );
cout<<"begin with :";
debug_show_set(rset[0]);
cout<<endl;
stack[top++] = 0;
if (contain_end( rset[0] ) )
end2.push_back(0);
while ( top )
{
top--;
int begin = stack[top];
for (int i=0;i<m;i++)//对每个输入符号 (边)都计算,应排除e边
if (i!=e_edge)
{
temp = rset[ begin ];
SI move_set = move(temp , i );
if (move_set.size() <=0)//如果对于某条边没有 输出的集合,应该不用计算
continue;
rset[n2] = e_closure( move_set );
int j;
for (j=0;j<n2;j++)
{
if ( rset[n2] == rset[ j ] )
break;
}
if (j!=n2)
{
rg[begin][i] = j;//不管是否产生新的子集,relation一定要记录
cout<<"A NEW EDGE AT RESULT IS "<<begin<<" ["<<edge[i]<<"] "<<j<<endl;//debug
continue;
}
rg[ begin ][ i ] = n2 ;
cout<<"A NEW EDGE AT RESULT IS "<<begin<<" ["<<edge[i]<<"] "<<n2<<endl;//debug
cout<<"FIND NEW SET :";debug_show_set( rset[n2] );cout<<endl;//debug
if (contain_end( rset[n2] ) )//检查是否包含结束状态
{
end2.push_back( n2 );
cout<<"END";//debug
}
stack[top++] = n2;
n2++;
}
}
}
void outputing()
{
int i,j;
cout<<endl;
for ( i=0;i<n2;i++ )
{
cout<<"set "<<i<<" : contain original status: ";
for (SI::iterator si=rset[ i ].begin(); si!=rset[ i ].end(); si++ )
cout<<original[ *si ]<<" ";
if ( start == i )
cout<<" start";
if ( find(end2.begin(),end2.end() , i ) !=end2.end() )
cout<<" end";
cout<<endl;
}
cout<<"realtions : "<<endl;
cout<<" ";
for (i=0;i<m;i++)
if (i!=e_edge)
cout<<edge[i]<<" ";
cout<<endl;
for ( i=0;i<n2;i++ )
{
cout<<char(i+'A')<<" ";
for (j=0;j<m;j++)
if (j==e_edge)
continue;
else if (rg[i][j]!=-1 )cout<<" "<<char('A'+rg[i][j])<<" ";
else cout<<" "<<'X'<<" ";
cout<<endl;
}
}
/*
如果遇到错误则终止判断,
如果在\0终止则判断 终止时的状态
不在 \0 终止 则一定不合法
*/
void work()
{
char str[N];
cout<<" 输入串 ";cin>>str;
int i,j;
int now;//目前状态
now = 0;
while (i<strlen(str) && now!=-1)
{
int temp = v[ str[ i ] ];
cout<<"to judge i "<<i<<" "<<str[i]<<" edge num:"<<temp<<endl;//debug
now = rg[now][temp];
i++;
}
if (str[i] == '\0')
{
if ( find(end2.begin(),end2.end(),now) != end2.end() )
{
cout<<"ANSWER IS TRUE"<<endl;
}
else cout<<"ANSWER IS WRONG"<<endl;
}
else cout<<"ANSWER IS WRONG"<<endl;
}
int main()
{
inputing();
memset(rg,-1,sizeof(rg));
find_sub_set();
outputing();
work();
return 0;
}
评论0