?? buildnfa.cpp
字號:
#include "Globals.h"
//#include "MainFrm.h"
//#include "AutoMakeView1.h"
int R=20;//節點半徑
int d=4*R;
list<int>::iterator CurrentIter=NULL;//當前演示指針
int xadd=80;//用于演示中x坐標的一次增減大小量
int yadd=50;//用于演示中y坐標的一次增減大小量
int startx=50,starty=300;//用于演示的結點的默認的坐標
//以下是NFA的數據結構
CString rExp;//正則表達式
LETTER_LIST letterlist;
NFA objNFA;
NODE_LIST* NFA_List=NULL;
int StateSum;//狀態總數
///////////////////////////////////
CNODE_LIST cnodelist;
/////////////////////////////
//視圖顯示
list<int> operations;
list<State> drawstates;
list<ARC> arcs;
CPoint* StatesPoints;
/*以下是正則表達式到NFA的幾個函數*/
void Translate(CString& r);//轉換正則表達式
void GetLetters(CString& r);//獲取字母表
void RToNFA(CString& r,NFA_LIST& NFAlist,CNODE_LIST &cnodelist,STATE_STACK &statestack);//正則表達式到NFA
void TranslateNFA(NFA_LIST& NFAlist);//改變NFA的存儲結構
void GetStatesPos(CPoint& pt);//獲取節點坐標
void ClearNFA()//清空數據結構里保存的東西
{
//////////////////
cnodelist.clear();
/////////////////////
letterlist.clear();
if(NFA_List!=NULL)
{
delete []NFA_List;
NFA_List=NULL;
}
operations.clear();
drawstates.clear();
arcs.clear();
if(StatesPoints!=NULL)
{
delete []StatesPoints;
StatesPoints=NULL;
}
}
bool BuildNFA(CString& r)//創建NFA
{
if(r.IsEmpty())
{
AfxMessageBox("請選擇一個正則表達式進行操作!\n(雙擊列表中的一項)");
return false;
}
CPoint pt(50,300);
NFA_LIST NFAlist;
//////////////////
STATE_STACK statestack;
//////////////////////
Translate(r);
GetLetters(r);
RToNFA(r,NFAlist,cnodelist,statestack);
TranslateNFA(NFAlist);
GetStatesPos(pt);
NFAlist.clear();
return true;
}
/*正則表達式到NFA的幾個函數的實現*/
void Translate(CString& r)//轉換正則表達式,主要把連接符號以'&'標識出來
{
list<char> chList;
int i=0;
r+='\0';
int n=r.GetLength();
///////////////////
int num=0;//用于計算y的初始坐標是多少
////////////////////////
while(i<n-1)//以鏈表把轉換后的正則表達式保存起來
{
chList.push_back(r[i]);
// if(r[i]>='a'&&r[i]<='z'||r[i]>='A'&&r[i]<='Z'||r[i]==')'||r[i]=='*')
if(r[i]!='('&&r[i]!='|')
//滿足此條件的字母后面加'&'
{
// if(r[i+1]>='a'&&r[i+1]<='z'||r[i+1]>='A'&&r[i+1]<='Z'||r[i+1]=='(')
if(r[i+1]!=')'&&r[i+1]!='*'&&r[i+1]!='|'&&r[i+1]!='\0')
chList.push_back('&');
}
/////////////////////
if(r[i]=='|')
{
num++;
}
////////////////
i++;
}
r.Empty();
list<char>::iterator iter;
for(iter=chList.begin();iter!=chList.end();iter++)
{
r+=*iter;
}
////////////////////
if(num>5)
{
starty=num*60;
}
////////////////////
chList.clear();//清空鏈表,釋放內存空間
}
void GetLetters(CString& r)
{
int i=0;
char letter[128];
memset(letter,0,128);
int n=r.GetLength();
while(i<n)
{
if(r[i]!='&'&&r[i]!='|'&&r[i]!='*'&&r[i]!='('&&r[i]!=')')
{
//letterlist.push_back(r[i]);
letter[r[i]]=r[i];
}
i++;
}
for(i=0;i<128;i++)
{
if(letter[i]!=0)
{
letterlist.push_back((char)letter[i]);
}
}
}
///////////////////////////////////////////////////////////////////
int max_(int a,int b)//返回兩者中的最大值
{
if(a>b)
return a;
else
return b;
}
int count(STATE_CHAIN &statechain)//用來計算狀態鏈表的狀態數
{
int num=0;
STATE_CHAIN::iterator iter;
for(iter=statechain.begin();iter!=statechain.end();iter++)
{
num++;
}
return num;
}
void X_ADD(CNODE_LIST &cnodelist,STATE_LIST &statelist,int n)//x方向上的增加量，用于畫圖的方法
{
int i;
CNODE_LIST::iterator iter;
STATE_LIST::iterator iter1;
NODE_LIST::iterator iter2;
for(iter1=statelist.begin();iter1!=statelist.end();iter1++)//對每一個結點的x值都增加值n
{
i=0;
iter=cnodelist.begin();
while(i!=*iter1)
{
iter++;
i++;
}
iter->x+=n;
}
}
void Y_ADD(CNODE_LIST &cnodelist,STATE_LIST &statelist,int n)//x方向上的增加量，用于畫圖的方法
{
int i;
CNODE_LIST::iterator iter;
STATE_LIST::iterator iter1;
NODE_LIST::iterator iter2;
for(iter1=statelist.begin();iter1!=statelist.end();iter1++)//對每一個結點的y值都增加值n
{
i=0;
iter=cnodelist.begin();
while(i!=*iter1)
{
iter++;
i++;
}
iter->y+=n;
}
}
CNode FIND(CNODE_LIST cnodelist,State n)//找某一狀態的坐標結點
{
int i=0;
CNODE_LIST::iterator iter;
iter=cnodelist.begin();
while(i!=n)
{
iter++;
i++;
}
return *iter;
}
///////////////////////////////////////////////////////////////////
NFA AddAnd(CNODE_LIST &cnodelist,STATE_STACK &statestack,NFA_LIST& NFAlist,NFA& val1,NFA& val2)//連接操作,返回新狀態的NFA
{
ARC tem;
NFA val;
int i;
NFA_LIST::iterator iter;
//////////////////////////////////
STATE_CHAIN::iterator iter1;
STATE_CHAIN statechain,statechain1,statechain2;
State state1,state2;
//////////////////////////////////
for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)//尋找第val1.end個節點
{
if(i==val1.end)//向此節點的相鄰節點鏈表加入一個節點
{
Node node;
node.state=val2.start;
node.symbol='\0';
iter->push_back(node);
operations.push_back(2);
tem.symbol='\0';
tem.start=val1.end;
tem.end=val2.start;
arcs.push_back(tem);
break;
}
}
val.start=val1.start;//以左操作數的開始狀態為初始狀態為新NFA的開始狀態
val.end=val2.end;//以右操作數的開始狀態為接受狀態為新NFA的接受狀態
///////////////////////////////////////
statechain1=statestack.back();
statestack.pop_back();//取狀態鏈表棧中的最頂不的鏈表
statechain2=statestack.back();
statestack.pop_back();
state1=statechain2.front();
state2=statechain2.back();
i=FIND(cnodelist,state2).x-FIND(cnodelist,state1).x+xadd;
X_ADD(cnodelist,statechain1,i);
// statechain.push_back(val.start);//合并經過運算的狀態鏈表
for(iter1=statechain2.begin();iter1!=statechain2.end();iter1++)
{
statechain.push_back(*iter1);
}
for(iter1=statechain1.begin();iter1!=statechain1.end();iter1++)
{
statechain.push_back(*iter1);
}
// statechain.push_back(val.end);
statestack.push_back(statechain);
statechain.clear();
statechain1.clear();
statechain2.clear();
///////////////////////////////////////
return val;
}
NFA AddOr(CNODE_LIST &cnodelist,STATE_STACK &statestack,NFA_LIST& NFAlist,NFA& val1,NFA& val2,State& StateNum)//選擇操作,返回新狀態的NFA
{
ARC tem;
NFA val;
int i;
NODE_LIST nodelist1,nodelist2;
Node node;
NFA_LIST::iterator iter;
//////////////////////////////////
STATE_CHAIN::iterator iter1,iter2;
STATE_CHAIN statechain,statechain1,statechain2;
State state1,state2;
CNode cnode;
//////////////////////////////////
node.state=val1.start;
node.symbol='\0';//添加一條空字符的轉換邊
nodelist1.push_back(node);
node.state=val2.start;
node.symbol='\0';//添加一條空字符的轉換邊
nodelist1.push_back(node);
NFAlist.push_back(nodelist1);//向鄰接表加入兩個新的鏈表
NFAlist.push_back(nodelist2);
operations.push_back(1);
drawstates.push_back(StateNum);
val.start=StateNum++;//新建兩個新的狀態
operations.push_back(1);
drawstates.push_back(StateNum);
val.end=StateNum++;
///////////////////////////////////////
statechain1=statestack.back();
statestack.pop_back();//取狀態鏈表棧中的最頂不的鏈表
statechain2=statestack.back();
statestack.pop_back();
X_ADD(cnodelist,statechain1,xadd);
X_ADD(cnodelist,statechain2,xadd);
Y_ADD(cnodelist,statechain1,yadd);
Y_ADD(cnodelist,statechain2,-yadd);
statechain.push_back(val.start);//合并經過運算的狀態鏈表
for(iter1=statechain1.begin();iter1!=statechain1.end();iter1++)
{
statechain.push_back(*iter1);
}
for(iter1=statechain2.begin();iter1!=statechain2.end();iter1++)
{
statechain.push_back(*iter1);
}
statechain.push_back(val.end);
statestack.push_back(statechain);
state1=statechain1.back();
state2=statechain2.back();
cnode.x=startx;
cnode.y=starty;
cnodelist.push_back(cnode);//添加一個該狀態的結點，定義在這個鏈表的開頭
cnode.x=max_(FIND(cnodelist,state1).x,FIND(cnodelist,state2).x)+xadd;
cnode.y=(FIND(cnodelist,state1).y+FIND(cnodelist,state2).y)/2;
cnodelist.push_back(cnode);
statechain.clear();
statechain1.clear();
statechain2.clear();
///////////////////////////////////////////////////////////
operations.push_back(2);
tem.symbol='\0';
tem.start=val.start;
tem.end=val1.start;
arcs.push_back(tem);
operations.push_back(2);
tem.symbol='\0';
tem.start=val.start;
tem.end=val2.start;
arcs.push_back(tem);
for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)
{
if(i==val1.end)//向此節點的相鄰節點鏈表加入一個節點
{
Node node;
node.state=val.end;
node.symbol='\0';//添加一條空字符的轉換邊
iter->push_back(node);
operations.push_back(2);
tem.symbol='\0';
tem.start=val1.end;
tem.end=val.end;
arcs.push_back(tem);
break;
}
}
for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)
{
if(i==val2.end)//向此節點的相鄰節點鏈表加入一個節點
{
Node node;
node.state=val.end;
node.symbol='\0';//添加一條空字符的轉換邊
iter->push_back(node);
operations.push_back(2);
tem.symbol='\0';
tem.start=val2.end;
tem.end=val.end;
arcs.push_back(tem);
break;
}
}
nodelist1.clear();//清空鏈表,釋放內存空間
return val;
}
NFA AddRepeat(CNODE_LIST &cnodelist,STATE_STACK &statestack,NFA_LIST& NFAlist,NFA& val1,State& StateNum)//閉包操作,返回新狀態的NFA
{
NFA val;
int i;
Node node;
NODE_LIST nodelist1,nodelist2;
NFA_LIST::iterator iter;
ARC tem;
////////////////////////////////////////////////////////
CNode cnode;
STATE_CHAIN::iterator iter1;
STATE_CHAIN statechain,statechain1;
State state;
/////////////////////////////////////////////////////////
operations.push_back(1);
drawstates.push_back(StateNum);
val.start=StateNum++;//新建兩個新的狀態
operations.push_back(1);
drawstates.push_back(StateNum);
val.end=StateNum++;
/////////////////////////////////////////////////
statechain1=statestack.back();
statestack.pop_back();//取狀態鏈表棧中的最頂不的鏈表
X_ADD(cnodelist,statechain1,xadd);
statechain.push_back(val.start);//合并經過運算的狀態鏈表
for(iter1=statechain1.begin();iter1!=statechain1.end();iter1++)
{
statechain.push_back(*iter1);
}
statechain.push_back(val.end);
statestack.push_back(statechain);
state=statechain1.back();
cnode.x=startx;
cnode.y=starty;
cnodelist.push_back(cnode);//添加一個該狀態的結點，定義在這個鏈表的開頭
cnode.x=FIND(cnodelist,state).x+xadd;
cnode.y=FIND(cnodelist,state).y;
cnodelist.push_back(cnode);
statechain.clear();
statechain1.clear();
///////////////////////////////////////////////////////////
node.state=val1.start;
node.symbol='\0';//添加一條空字符的轉換邊
nodelist1.push_back(node);
operations.push_back(2);
tem.symbol='\0';
tem.start=val.start;
tem.end=val1.start;
arcs.push_back(tem);
node.state=val.end;
node.symbol='\0';//添加一條空字符的轉換邊
nodelist1.push_back(node);
operations.push_back(3);
tem.symbol='\0';
tem.start=val.start;
tem.end=val.end;
arcs.push_back(tem);
NFAlist.push_back(nodelist1);//向鄰接表加入兩個新的鏈表
NFAlist.push_back(nodelist2);
for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)
{
if(i==val1.end)
{
Node node;
node.state=val1.start;
node.symbol='\0';//添加一條空字符的轉換邊
iter->push_back(node);
operations.push_back(3);//添加一個操作,1.為節點生成操作2.為直線邊3.為曲線邊
tem.symbol='\0';
tem.start=val1.end;
tem.end=val1.start;
arcs.push_back(tem);
node.state=val.end;
node.symbol='\0';//添加一條空字符的轉換邊
iter->push_back(node);
operations.push_back(2);//添加一個操作,1.為節點生成操作2.為直線邊3.為曲線邊
tem.symbol='\0';
tem.start=val1.end;
tem.end=val.end;
arcs.push_back(tem);
break;
}
}
nodelist1.clear();//清空鏈表,釋放內存空間
return val;
}
void RToNFA(CString& r,NFA_LIST& NFAlist,CNODE_LIST &cnodelist,STATE_STACK &statestack)//正則表達式到NFA
{
///////////////////
STATE_CHAIN statechain;
///////////////////////
list<NFA> l1;//NFA棧,NFA保存的是一個NFA的開始狀態和終止狀態
list<Symbol> l2;//符號棧,用于保存正則表達式運算符
int i=0;//標志當前字符在正則表達式字符串中的位置
char ch;//暫存出棧字符
NFA val1,val2,val;//保存NFA運算操作數和結果
State StateNum=0;//當前狀態數
ARC tem;
int n=r.GetLength();
while(i<n)//如果正則表達式還沒結束,do
{
// if(r[i]>='a'&&r[i]<='z'||r[i]>='A'&&r[i]<='Z')//遇到正則表達式
if(r[i]!='('&&r[i]!=')'&&r[i]!='*'&&r[i]!='|'&&r[i]!='&')
{
NODE_LIST nodelist1;
NODE_LIST nodelist2;
////////////////////////////////
CNode cnode;
///////////////////////////////
// NFA nfa;
Node node;
operations.push_back(1);//添加一個操作,1.為節點生成操作2.為直線邊3.為曲線邊
drawstates.push_back(StateNum);
val.start=StateNum++;//新建兩個新的狀態
operations.push_back(1);//添加一個操作,1.為節點生成操作2.為直線邊3.為曲線邊
drawstates.push_back(StateNum);
node.state=val.end=StateNum++;
node.symbol=r[i];
l1.push_back(val);//nfa進棧
///////////////////////////////////
cnode.x=startx;
cnode.y=starty;
cnodelist.push_back(cnode);
cnode.x=startx+xadd;
cnode.y=starty;
cnodelist.push_back(cnode);
statechain.push_back(val.start);//添加兩個狀態組成的鏈表
statechain.push_back(val.end);
statestack.push_back(statechain);
statechain.clear();
/////////////////////////////////////
tem.symbol=r[i];
tem.start=val.start;
tem.end=val.end;
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -