#include "dfa.h"

//输入DFA
void DFA::input()
{
	//输入状态集
	cout<<"状态集:";
	int i=0;
	do{
		cin>>q[i];
		i++;
	}while(getchar()!='\n');
	num_q=i;	//状态个数
	i=0;
	//cout<<"num_q="<<num_q<<endl;	//调试输出
	
	//输入字母表
	cout<<"字母表:";
	do{
		cin>>sigma[i];
		i++;
	}while(getchar()!='\n');
	num_sigma=i;	//字符数
	i=0;
	//cout<<"num_sigma="<<num_sigma<<endl;
	
	//输入转移矩阵
	cout<<"转移函数:"<<endl;
	for(int i=0;i<num_q;i++)
		for(int j=0;j<num_sigma;j++)
			cin>>delta[i][j];
	
	//起始状态
	cout<<"起始状态:";
	cin>>q0;
	
	//接受状态集
	cout<<"接受状态集:";
	do{
		cin>>f[i];
		i++;
	}while(getchar()!='\n');
	num_f=i;	//接受状态个数
	i=0;
	//cout<<"num_f="<<num_f<<endl;
		
}

//输出DFA
void DFA::print_dfa()
{
	cout<<"您输入五元组为："<<endl;
	cout<<"{{";
	for(int i=0;i<num_q;i++)
	{
		cout<<q[i];
		if(i<num_q-1)
			cout<<",";
	}
	cout<<"},{";
	for(int i=0;i<num_sigma;i++)
	{
		cout<<sigma[i];
		if(i<num_sigma-1)
			cout<<",";
	}
	cout<<"},{";
	for(int i=0;i<num_q;i++)
		for(int j=0;j<num_sigma;j++)
		{
			
			cout<<delta[i][j];
			if(j+1==num_sigma)
				cout<<",";
			else
				cout<<" ";
			
		}
	cout<<"},";
	cout<<q0<<",{";
	for(int i=0;i<num_f;i++)
	{
		cout<<f[i];
		if(i<num_f-1)
			cout<<",";
	}
	cout<<"}}"<<endl;
	
}

//DFA规则字符串判断
void DFA::judge(char *str)
{
	int i=0;
	int str_lenght;	//待测串长度
	str_lenght=strlen(str);
	
	cout<<"您输入的字符串为:";
	cout<<str<<endl;
	
	//找出q0在状态集中的位置
	int loca_q0;
	for(loca_q0=0;i<num_q;loca_q0++)
	{
		if(q[loca_q0]==q0)
			break;
	}
	char tmp;
	tmp=q[loca_q0];	//最开始为起始状态
	cout<<"\n状态转移过程为："<<endl;
	for(unsigned int j=0;j<str_lenght;j++)
	{
		//找出str[j]在字母表中的位置
		int order=0;
		int flags=0;	//标志是否在字母表中找到字符
		for(order=0;order<num_sigma;order++)
		{
			if(str[j]==sigma[order])
			{
				flags=1;	//在字母表中找到字符
				break;
			}
		}
		//如果字符不在字母表中，返回错误
		if(flags!=1)
		{
			cout<<"DFA不接受该串(存在不在字母表中的字符)!"<<endl;
				return;
		}
		flags=0;	//重置为0继续用于标志状态是否在状态集中
		int i=0;
		//找出状态在状态集合中的位置
		int locat=0;
		for(locat=0;locat<num_q;locat++)
		{
			if(tmp==q[locat])
			{
				flags=1;
				break;
			}
		}
		//如果状态不在状态集中，返回错误
		if(flags!=1)
		{
			cout<<"DFA不接受该串!(转移矩阵错误)"<<endl;
				return;
		}
		if(delta[locat][order]=='-')
		{
			cout<<"DFA不接受该串.(空状态)"<<endl;
			return;
		}
		else
		{
			//cout<<"order="<<order<<endl;
			cout<<"状态 "<<q[locat]<<" 经 "<<str[j]<<" 到状态 "<< delta[locat][order]<<endl;
			tmp=delta[locat][order];		//DFA运行
		}
	}
	//DFA停止状态测试输出
	cout<<"停止状态:"<<tmp<<endl;
	cout<<endl;
	for(int j=0;j<num_f;j++)
	{
		if(tmp==f[j])
			cout<<"DFA接受"<<str<<" ? : YES"<<endl;
		else
			cout<<"DFA接受"<<str<<" ? : NO"<<endl;
	}
}

//写五元组到文件
void DFA::write()
{
	ofstream out;
	out.open("data.dfa");
	if(!out)
	{
		cout<<"文件打开错误!"<<endl;
		return;
	}
	//写入状态集
	for(int i=0;i<num_q;i++)
	{
		out<<q[i];
		if(i<num_q-1)
			out<<" ";
	}
	out<<endl;
	
	//写入字母表
	for(int i=0;i<num_sigma;i++)
	{
		out<<sigma[i];
		if(i<num_sigma-1)
			out<<" ";
	}
	out<<endl;
	
	//写入转移矩阵
	for(int i=0;i<num_q;i++)
	{
		for(int j=0;j<num_sigma;j++)
		{
			
			out<<delta[i][j];
			if((j+1)%num_sigma==0)
				out<<endl;
			else
				out<<" ";
		}
	}
	
	//写入初始状态
	out<<q0<<endl;
	
	//写入接受状态集
	for(int i=0;i<num_f;i++)
	{
		out<<f[i];
		if(i<num_f-1)
			out<<" ";
	}
	out<<endl;
	out.close();
}

//从文件中读取五元组
int DFA::read()
{
	ifstream fin;
	fin.open("data.dfa");
	if(!fin)
	{
		cout<<"打开data.dfa失败，请先执行步骤2"<<endl;
		return 0;
	}
	
	//输入状态集
	int i=0;
	while(fin.get(q[i]))
	{
		if(q[i]==' ')
			continue;
		if(q[i]=='\n')
			break;
		cout<<q[i]<<" ";
		i++;
	}
	cout<<endl;
	num_q=i;	//状态个数
	i=0;
	//cout<<"num_q="<<num_q<<endl;	//调试输出
	
	//输入字母表
	while(fin.get(sigma[i]))
	{
		if(sigma[i]==' ')
			continue;
		if(sigma[i]=='\n')
			break;
		cout<<sigma[i]<<" ";
		i++;
	}
	cout<<endl;
	num_sigma=i;	//字符数
	i=0;
	//cout<<"num_sigma="<<num_sigma<<endl;
	
	//输入转移矩阵
	for(int i=0;i<num_q;i++)
		for(int j=0;j<num_sigma;j++)
		{
			if(delta[i][j]==' '||delta[i][j]=='\n')
				continue;
			fin>>delta[i][j];
			cout<<delta[i][j]<<" ";
			if(j+1==num_sigma)
				cout<<endl;
		}
	
	//起始状态
	fin>>q0;
	fin.get();
	cout<<q0<<endl;
	
	//接受状态集
	while(fin.get(f[i]))
	{
		if(f[i]==' ')
			continue;
		if(f[i]=='\n')
			break;
		cout<<f[i]<<" ";
		i++;
	}
	cout<<endl;
	num_f=i;	//接受状态个数
	i=0;
	//cout<<"num_f="<<num_f<<endl;
	return 1;
}

//DFA正确性检查
int DFA::check()
{
	//检查状态集元素的唯一性
	for(int i=0;i<num_q;i++)
	{
		for(int j=i+1;j<num_q;j++)
		{
			if(q[i]==q[j])
			{
				cout<<"状态集元素不唯一！请检查输入"<<endl;
				return 0;
			}
		}
	}
	
	//检查字母表元素的唯一性
	for(int i=0;i<num_sigma;i++)
	{
		for(int j=i+1;j<num_sigma;j++)
		{
			if(sigma[i]==sigma[j])
			{
				cout<<"字母表元素不唯一! 请检查输入"<<endl;
				return 0;
			}
		}
	}
	
	//检查转移矩阵
	int flags=0;
	for(int i=0;i<num_q;i++)
	{
		for(int j=0;j<num_sigma;j++)
		{
			for(int k=0;k<num_q;k++)
			{
				if((delta[i][j]==q[k])||(delta[i][j]=='-')) 	//转移矩阵元素在状态集中
				{
					flags=1;
					break;
				}
				flags=0;	//重置flags
			}
			if(flags!=1)
			{
				cout<<"转移矩阵中存在不在状态集或不为'-'的元素! 请检查输入"<<endl;
				return 0;
			}
		}
	}
	
	//检查开始状态是否在状态集中
	flags=0;
	for(int i=0;i<num_q;i++)
	{
		if(q0==q[i])
		{
			flags=1;
			break;
		}
	}
	if(flags!=1)
	{
		cout<<"起始状态不在状态集中! 请检查输入"<<endl;
		return 0;
	}
	
	//检查接受状态集是否唯一
	for(int i=0;i<num_f;i++)
	{
		for(int j=i+1;j<num_f;j++)
		{
			if(f[i]==f[j])
			{
				cout<<"接受状态集元素不唯一! 请检查输入"<<endl;
				return 0;
			}
		}
	}
	
	//检查接受状态集是否在状态集中
	flags=0;
	for(int i=0;i<num_f;i++)
	{
		for(int j=0;j<num_q;j++)
		{
			if(f[i]==q[j])
			{
				flags=1;
				break;
			}
		}
		if(flags!=1)
		{
			cout<<"接受状态集有元素不包含在状态集中! 请检查输入"<<endl;
			return 0;
		}
	}
	cout<<"各集合元素唯一...."<<endl;
	cout<<"开始状态唯一,并包含在状态集中...."<<endl;
	cout<<"接受状态集元素在状态集中...."<<endl;
	cout<<"状态转换表正确...."<<endl;
	cout<<"DFA 通过正确性检查"<<endl;
	return 1;
}

//不显示调试信息的DFA规则字符串判断
int DFA::simple_judge(char *str)
{
	int i=0;
	int str_lenght;	//待测串长度
	str_lenght=strlen(str);
	//找出q0在状态集中的位置
	int loca_q0;
	for(loca_q0=0;i<num_q;loca_q0++)
	{
		if(q[loca_q0]==q0)
			break;
	}
	char tmp;
	tmp=q[loca_q0];	//最开始为起始状态
	for(unsigned int j=0;j<str_lenght;j++)
	{
		//找出str[j]在字母表中的位置
		int order=0;
		int flags=0;	//标志是否在字母表中找到字符
		for(order=0;order<num_sigma;order++)
		{
			if(str[j]==sigma[order])
			{
				flags=1;	//在字母表中找到字符
				break;
			}
		}
		//如果字符不在字母表中，返回错误
		if(flags!=1)
		{
				return 0;
		}
		flags=0;	//重置为0继续用于标志状态是否在状态集中
		int i=0;
		//找出状态在状态集合中的位置
		int locat=0;
		for(locat=0;locat<num_q;locat++)
		{
			if(tmp==q[locat])
			{
				flags=1;
				break;
			}
		}
		//如果状态不在状态集中，返回错误
		if(flags!=1)
		{
				return 0;
		}
		if(delta[locat][order]=='-')
		{
			return 0;
		}
		else
		{
			//cout<<"order="<<order<<endl;
			tmp=delta[locat][order];		//DFA运行
		}
	}
	for(int j=0;j<num_f;j++)
	{
		if(tmp==f[j])
			return 1;
		else
			return 0;
	}
}


//得到所字母表组成的所有字符串有列表
void DFA::get_str(int k,vector<char> v)
{
	
	if(k>0)
    { 
        for(int i=0;i<num_sigma;i++)
        {
            v.push_back(sigma[i]);
            if(k==1)
            {
				char *tmp;
				tmp=new char[v.size()+1];
                for(int j=0;j<v.size();j++)
				{
					tmp[j]=v[j];
						//cout<<v[j];
				}
				tmp[v.size()]='\0';		//数组结束
				if(simple_judge(tmp))
				{
					cout<<tmp<<endl;
                }
				delete []tmp;
				
            }
            else
            {
                get_str(k-1,v);
            }
            v.pop_back();       
        }
    } 
}

//显示语言集列表
void DFA::collection()
{

	vector<char> v;
	int n;	//字符串最大长度
	cout<<"请输入字符串最大长度:";
	cin>>n;
	cout<<"\n该DFA的语言集为:\n";
    for(int i=1;i<n+1;i++)
    {
        get_str(i,v); 
        v.clear();   
    }
}