📄 正规式.cpp
字号:
}
}
if(Second.size()!=0 )
{
if( exist_str(Second, tab)==-1 )
{
tab->push_back(Second);
Node *new_node1=new Node(state[1]++);
(*N2)[i]->setnext(condition[j], new_node1);
N2->push_back(new_node1);
}
else
{
int sure=exist_str(Second, tab);
(*N2)[i]->setnext(condition[j], (*N2)[sure]);
}
}
}
}
for(i=0; i<tab->size(); i++) //显示tab表
{
for(int j=0; j<(*tab)[i].size(); j++)
{
cout<<(*tab)[i][j];
}
cout<<"\t";
}
}
bool exist(vector <char> a, char c2)
{
for(int i=0; i<a.size(); i++)
{
if(a[i]==c2) return true;
}
return false;
}
int exist_str(vector <char> Second, vector < vector <char> > *tab )
{
for(int i=0; i<tab->size(); i++)
{
if(Second.size()==(*tab)[i].size() )
{
for(int k=0; k<Second.size(); k++)
{
if( !exist((*tab)[i], Second[k]) )
{
break;
}
}
if( k==Second.size() )
{
return i;
}
}
}
return -1;
}
void to_bibao(char state, char condition, vector <char> *Second, vector <Node*> *N)
{
for(int j=0; j<N->size(); j++)
{
if(state==(*N)[j]->getd() )
{
for(int i=0; i<(*N)[j]->L.size(); i++)
{
char ch=(*N)[j]->L[i]->get_c();
if(ch==condition)
{
char c2=(*N)[j]->L[i]->next->getd();
if( !exist(*Second, c2) ) //如果 !(a中存在c2)
{
Second->push_back(c2);
to_bibao(c2, '~', Second, N);
}
}
}
}
}
}
void Init_condition(vector <char> *condition, vector <Node*> *N)
{
for(int i=0; i<N->size(); i++)
{
for(int j=0; j<(*N)[i]->L.size(); j++)
{
char ch=(*N)[i]->L[j]->get_c();
if( !exist( *condition, ch ) && ch!='~' )
{
condition->push_back( ch );
}
}
}
}
void DFA_min(vector <Node*> *N2, vector <Node*> *N3, vector < vector <char> > *tab)
{
vector< vector<int> > sunset; //子集表
vector< vector<char> > csunset;
vector<char> condition;
Init_condition(&condition, N2);
Init_sonset(&sunset, &csunset, tab, N2);
vector<char> First; //指向集
// 以下为建立sunset表
for(int i=0; i<sunset.size(); i++) //基本分化集合层
{
if(sunset[i].size()>1 )
{
for(int k=0; k<condition.size(); k++) //条件层
{
int overL=0;
First.clear();
for(int j=0; j<sunset[i].size(); j++) //某子集层
{
if( k<(*N2)[sunset[i][j]]->L.size() ) //若存在L[k]
{
char ch1=(*N2)[sunset[i][j]]->L[k]->next->getd();
First.push_back(ch1);
}
else First.push_back('#');
}
if(contain(First, csunset) ) { }
else
{
divideset(i, k, &sunset, &csunset, N2);
k=condition.size(); //终止2循环
i--;
}
}
}
}
for(i=0; i<csunset.size(); i++)
{
for(int j=0; j<csunset[i].size(); j++)
{
cout<<csunset[i][j];
}
cout<<"\t";
}
cout<<endl;
vector<char> newc;
for(i=0; i<csunset.size(); i++)
{
Node *new_node1=new Node(csunset[i][0]);
newc.push_back(csunset[i][0]);
N3->push_back(new_node1);
}
// 以下为建立N3向量
for(i=0; i<N2->size(); i++)
{
char c1=(*N2)[i]->getd();
char c2;
char ccondition;
for(int j=0; j<(*N2)[i]->L.size(); j++)
{
ccondition=(*N2)[i]->L[j]->get_c();
c2=(*N2)[i]->L[j]->next->getd();
int flag1, flag2;
if(exist(newc, c1)) //若c1为非删除结点
{
for(int k=0; k<newc.size(); k++)
{
if(newc[k]==c1)
{
flag1=k;
break;
}
}
if( exist(newc, c2) ) //若c2为非删除结点
{
for(int k=0; k<newc.size(); k++)
{
if(newc[k]==c2)
{
flag2=k;
break;
}
}
}
else if(!exist(newc, c2) ) //若c2为删除结点
{
for(int k=0; k<csunset.size(); k++)
{
if(exist(csunset[k], c2) )
{
flag2=k;
}
}
}
}
else if(!exist(newc, c1)) //若c1为删除结点
{
for(int k=0; k<csunset.size(); k++)
{
if(exist(csunset[k], c1) )
{
flag1=k;
}
}
if( exist(newc, c2) ) //若c2为非删除结点
{
for(int k=0; k<newc.size(); k++)
{
if(newc[k]==c2)
{
flag2=k;
break;
}
}
}
else if(!exist(newc, c2) ) //若c2为删除结点
{
for(int k=0; k<csunset.size(); k++)
{
if(exist(csunset[k], c2) )
{
flag2=k;
}
}
}
}
int flag3=0;
for(int m=0; m<(*N3)[flag1]->L.size(); m++)
{
if( (*N3)[flag1]->L[m]->get_c()==ccondition )// 条件相同
{
if( (*N3)[flag1]->L[m]->next->getd()==(*N3)[flag2]->getd()) //指向相同
{
flag3=1;
}
}
}
if(flag3==0)
{
(*N3)[flag1]->setnext(ccondition, (*N3)[flag2] );
}
}
}
}
void divideset(int key, int k, vector< vector<int> > *sunset, vector< vector<char> > *csunset, vector <Node*> *N2)
{
vector <int> ssunset;
vector <char> sonset;
vector<int> like;
if( k<(*N2)[ (*sunset)[key][0] ]->L.size() )
{
for(int i=0; i<(*sunset)[key].size(); i++)
{
char c=(*N2)[ (*sunset)[key][i] ]->L[k]->next->getd();
sonset.push_back(c);
}
int flag=0; //确定与sonset[0]所在子集
for(i=0; i<csunset->size(); i++)
{
if( exist((*csunset)[i], sonset[0]) )
{
flag=i;
break;
}
}
//确定与sonset[0]所在子集相同的字符下标
for(i=0; i<sonset.size(); i++)
{
if( exist((*csunset)[flag], sonset[i]) )
{
like.push_back(i);
}
}
}
else
{
like.push_back(0);
}
vector <int> first;
vector <int> rest;
vector <char> cfirst;
vector <char> crest;
for(int i=0; i<like.size(); i++) //得到1个子集
{
first.push_back((*sunset)[key][like[i]]);
}
for(i=0; i<first.size(); i++) //字符子集1
{
char c=(*N2)[ first[i] ]->getd();
cfirst.push_back(c);
}
for(i=0; i<(*csunset)[key].size(); i++) //字符子集1
{
if( !exist(cfirst, (*csunset)[key][i]) )
{
crest.push_back((*csunset)[key][i]);
rest.push_back((*sunset)[key][i]);
}
}
sunset->erase( sunset->begin()+key);
csunset->erase( csunset->begin()+key);
sunset->push_back(first);
sunset->push_back(rest);
csunset->push_back(cfirst);
csunset->push_back(crest);
}
bool contain(vector <char> First, vector< vector<char> > csunset)
{
int flag=-1;
for(int j=0; j<csunset.size(); j++)
{
if( exist(csunset[j], First[0]) )
{
flag=j;
break;
}
}
if(flag==-1) return false;
else
{
for(int i=0; i<First.size(); i++)
{
if(!exist(csunset[flag], First[i]) ) break;
}
if(i==First.size() ) return true;
else return false;
}
}
void Display(vector <Node*> N)
{
cout<<"\n";
for(int i=0; i<N.size(); i++)
{
cout<<N[i]->getd()<<"\t";
N[i]->display();
cout<<endl;
}
}
void Init_sonset(vector < vector<int> > *sunset, vector < vector<char> > *csunset, vector < vector<char> > *tab, vector <Node*> *N2)
{
vector<int> final;
vector<int> notfinal;
for(int i=0; i<tab->size(); i++)
{
if(exist((*tab)[i], 'Y') )
{
final.push_back( i );
}
else
{
notfinal.push_back( i );
}
}
sunset->push_back(final);
sunset->push_back(notfinal);
for(i=0; i<sunset->size(); i++)
{
vector <char> cc;
cc.clear();
for(int j=0; j<(*sunset)[i].size(); j++)
{
char c=(*N2)[(*sunset)[i][j]]->getd();
cc.push_back(c);
}
csunset->push_back(cc);
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -