26-08-2008, 10:53 PM
توضیح اضافی ندارم اگه کسی خواست بدونه چطوری کار می کنه و کد رو نفهمید بگه
macro.h
dfa.h
test.cpp
input data in.in
6
2 4
ab
3 1
5 2
2 3
2 4
2 5
4 2
aabbababba
کد:
#ifndef MACRO_H
#define MACRO_H
#define ALL(x) (x).begin(),(x).end()
#define ForEach(x,it) for(it=(x).begin() ; (x).end() != it ; ++it)
#define ForToEach(x,it,end) for(it=(x).begin() ; (end) != it ; ++it)
#define F2Each(x,it,y,jt) for(it=(x).begin(),jt=(y).begin() ; (x).end() != it ; ++it, ++jt)
#define IsIn(continer,elem) find(ALL(continer),elem)!=(continer).end()
#define For(i,n) for(unsigned i=0; i < n ;++i)
#define SEE(x) cerr<<(x)<<endl;
#define IF(cond,t,f) (cond)? (t) : (f)
#endifdfa.h
کد:
/**
@author M.J <arash_j13> arash.j13-replace with @ -gmail-dot-com
20 Aug 2008
Mashhad
DFA class
part of myRegularExpression library
*/
#ifndef DFA_H
#include <vector>
#include <map>
#include <list>
#include <cassert>
#include <algorithm>
#include <string>
#include <string>
#include "macro.h"
using namespace std;
string ToS(unsigned);
class DFA
{
public:
typedef unsigned State;
typedef char Char;
typedef list<State> Cell;
typedef map<Char,Cell> Row;
typedef list<Char> AlphabetSet;
typedef list<State> AcceptSet;
typedef vector<Row> FunctionType;
typedef string Input;
private:
AlphabetSet alphabet;
AcceptSet accepts;
FunctionType function;
unsigned state_cnt;
State start;
const State NO_ACTION;
public:
DFA(unsigned cnt,const AlphabetSet &a,const AcceptSet &ac,const FunctionType &f,State s=0)
:NO_ACTION(INT_MAX)
{
alphabet=a;
if(check_accept(ac,cnt) && check_function(f,cnt) && s<cnt)
{
start=s;
state_cnt=cnt;
accepts=ac;
function=f;
}
}
private:
bool check_accept(const AcceptSet &ac,unsigned n) const
{
AcceptSet::const_iterator it;
for(it=ac.begin();ac.end()!=it;++it)
{
if(*it>=n)
return false;
}
return true;
}
bool check_function(const FunctionType &f,unsigned n) const
{
FunctionType::const_iterator rt;
Row::const_iterator ct;
Cell::const_iterator it;
ForEach(f,rt)
{
ForEach(*rt,ct)
{
if(!inAlphabet(ct->first))
return false;
ForEach(ct->second,it)
{
if(*it>=n)
return false;
}
}
}
return true;
}
bool inAlphabet(Char ch) const
{
return IsIn(alphabet,ch);
}
bool inAccept(State s) const
{
return IsIn(accepts,s);
}
bool possible(State s,Char input) const
{
Row::const_iterator ct;
ct=function[s].find(input);
assert(ct!=function[s].end());
return !ct->second.empty();
}
DFA::State where(State cur,Char input) const
{
Row::const_iterator ct;
ct=function[cur].find(input);
assert(ct!=function[cur].end());
if(ct->second.empty())
return NO_ACTION;
return ct->second.front();
}
public:
bool match(Input input) const
{
State cur=start;
Input::iterator it;
ForEach(input,it)
{
if(possible(cur,*it))
cur=function[cur].find(*it)->second.front();
else
return false;
}
return inAccept(cur);
}
void optimize()
{
vector<unsigned> group(state_cnt);
vector<vector<State> > elements(2);
vector<bool> modify(2,false);
vector<map<Char,State> > newfunc(2);
AcceptSet::iterator el;
ForEach(accepts,el)
{
group[*el]=1;
elements[1].push_back(*el);
}
For(i,state_cnt)
{
if(group[i]==0)
elements[0].push_back(i);
}
vector<unsigned> tmp;
vector<vector<State> >::iterator gr;
vector<State>::iterator st;
vector<unsigned>::iterator it;
AlphabetSet::iterator al;
for(bool br=true;br;)
{
br=false;
//ForEach(elements,gr)
#define Correction() gr=elements.begin()+_j
#define CUR gr-elements.begin()
For(_j,elements.size())
{
Correction();
if(gr->size()<2)
{
ForEach(alphabet,al)
{
DFA::State next=where(gr->front(),*al);
newfunc[CUR][*al]=IF(next==NO_ACTION,next,group[next]);
}
continue;
}
ForEach(alphabet,al)
{
map<Char,State>::iterator wh=newfunc[CUR].find(*al);
if(wh!=newfunc[CUR].end())
{
State next=wh->second;
if(next==NO_ACTION || modify[next]==false)
continue;
}
tmp.clear();
ForEach(*gr,st)
{
State next=where(*st,*al);
if(next==NO_ACTION)
{
tmp.push_back(NO_ACTION);
}
else
{
tmp.push_back(group[next]);
}
}
assert(tmp.size()>1 && tmp.size()==gr->size());
sort(ALL(tmp));
unsigned pre=tmp[0];
vector<State> newlist;
For(i,tmp.size())
{
if(tmp[i]!=pre)
{
if(newlist.size() && newlist[0]!= gr->at(0)) //first group no need to change
{
br=true;
remove(*gr,newlist);
elements.push_back(newlist);
gr=Correction();
modify[gr-elements.begin()]=true;
modify.push_back(true);
unsigned new_group=elements.size()-1;
ForEach(newlist, st)
{
group[*st]=new_group;
}
newfunc.push_back(newfunc[CUR]);
newfunc[new_group][*al]=pre;
}
else
{
newfunc[CUR][*al]=pre;
}
newlist.clear();
pre=tmp[i];
}
newlist.push_back(gr->at(i));
}
if(newlist.size()!=gr->size())
{
br=true;
remove(*gr,newlist);
elements.push_back(newlist);
Correction();
modify[CUR]=true;
modify.push_back(true);
unsigned new_group=elements.size()-1;
ForEach(newlist, st)
{
group[*st]=new_group;
}
newfunc.push_back(newfunc[CUR]);
newfunc[new_group][*al]=pre;
}
else
{
newfunc[CUR][*al]=pre;
}
#undef Correction
#undef CUR
}
}
}
refreshDFA(newfunc,elements);
}
private:
void remove(vector<State> & src,const vector<State> &vals)
{
vector<State> result;
vector<State>::const_iterator it,jt;
ForEach(vals,it)
{
result.clear();
ForEach(src,jt)
{
if(*jt!=*it)
result.push_back(*jt);
}
src=result;
}
}
void refreshDFA(const vector<map<Char,State> > & newfunc,const vector<vector<DFA::State> > & elements)
{
function.clear();
function.resize(newfunc.size());
vector<map<Char,State> >::const_iterator row;
map<Char,State>::const_iterator cell;
FunctionType::iterator rt;
vector<vector<DFA::State> >::const_iterator gr;
F2Each(newfunc,row,function,rt)
{
ForEach(*row,cell)
{
DFA::Cell &ct=rt->operator [](cell->first);
if(cell->second!=NO_ACTION)
ct.push_back(cell->second);
}
}
DFA::AcceptSet newaccepts;
ForEach(elements,gr)
{
if(inAccept(gr->front()))
{
newaccepts.push_back(gr-elements.begin());
}
}
accepts=newaccepts;
}
public:
ostream &showDFA(ostream & out)
{
#define cout ERROR_
out<<"Alphabeta: {";
string sep="";
DFA::AlphabetSet::iterator al;
ForEach(alphabet,al)
{
out<<sep<<*al;
sep=", ";
}
out<<"}"<<endl<<endl;
out<<"Accepts :{";
sep="";
DFA::AcceptSet::iterator ac;
ForEach(accepts,ac)
{
out<<sep<<*ac;
sep=" ,";
}
out<<"}"<<endl;
#define CUR row-function.begin()
DFA::FunctionType::iterator row;
ForEach(function,row)
{
out<<endl;
DFA::Row::iterator cell;
ForEach(*row,cell)
{
string des=IF(cell->second.empty(),"NULL",ToS(cell->second.front()));
out<<"f("<<CUR<<" , "<<cell->first<<") = "<<des<<endl;
}
}
return out;
#undef CUR
#undef cout
}
};
inline string ToS(unsigned x)
{
char buf[100];
_ltoa_s(x,buf,10);
return buf;
};
#endiftest.cpp
کد:
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <sstream>
#include <fstream>
#include "macro.h"
#include "dfa.h"
using namespace std;
void readinput(istream &in,unsigned &cnt,DFA::AcceptSet &acc,
DFA::AlphabetSet &alpha, DFA::FunctionType &func)
{
acc.clear();
alpha.clear();
func.clear();
string line;
in>>cnt;
in.ignore();
getline(in,line);
stringstream stin;
stin<<line;
for(unsigned x; stin>>x; acc.push_back( static_cast<DFA::State>(x) )) ;
stin.clear();
getline(in,line);
stin<<line;
for(char ch; stin>>ch; alpha.push_back( static_cast<DFA::Char>(ch) )) ;
DFA::FunctionType::iterator rt;
func.resize(cnt);
ForEach(func,rt)
{
DFA::AlphabetSet::iterator at;
ForEach(alpha,at)
{
int x;
DFA::Cell &cell=rt->operator [](*at);
in>>x;
if(x>=0)
{
cell.push_back(x);
}
}
}
}
int main()
{
ifstream fin("dfa.in");
DFA::FunctionType f;
DFA::AlphabetSet al;
DFA::AcceptSet ac;
unsigned cnt=0;
readinput(fin,cnt,ac,al,f);
DFA fa(cnt,al,ac,f);
fa.optimize();
fa.showDFA(cout);
string line;
fin.ignore();
getline(fin,line);
cout<<endl<<"input :"<<line<<" : "<<boolalpha<<fa.match(line)<<endl<<endl;
}input data in.in
6
2 4
ab
3 1
5 2
2 3
2 4
2 5
4 2
aabbababba
واقعا نمیدونم باید چیکار کنم...لطفا جوابمو بدین....