?? compile_work2.cpp
字號:
#include "iostream.h"
#include "string.h"
//////////////////////////////////////////////////////////////////////////
////////////////// Begin Regular==>NFA ////////////////////////////////
struct Relation //定義NFA中弧
{
int CurrentState; //定義起始狀態
int NextState; //定義下一個狀態
char TransitionElement; //定義輸入字符
};
struct TokenState //定義操作符號處理棧
{
int BeginState; //定義起始
int EndState; //定義結束
int preposition; //定義記錄（一個大的區域）狀態開始時在波蘭式中的位置
};
int IsTransitionElement(char s) //判斷輸入字符串是否合法
{
if (s=='0'||s=='1'||s=='$')
return 1;
else return 0;
}
void NFADiagram(Relation *Rstring,int position,int CurrentState,
int NextState,char TransitionElement) //生成NFA中弧的信息
{
Rstring[position].CurrentState=CurrentState;
Rstring[position].NextState=NextState;
Rstring[position].TransitionElement=TransitionElement;
}
int TokenDealing(char *string,int position,TokenState *token,int *Rtoken)//雙目運算
{
if (IsTransitionElement(string[position]) //型如 “輸入字符 輸入字符 操作符”
&&IsTransitionElement(string[position-1]))
return 0;
else if (IsTransitionElement(string[position]) //型如 “輸入字符 操作符 輸入字符”
&&!IsTransitionElement(string[position-1]))
return 1;
else //查找在波蘭式中區域的開始字符
{
int firsttoken=token[Rtoken[position]].preposition;
if(IsTransitionElement(string[firsttoken-1]))
return 2; //型如 “輸入字符 |” 如果前一區域的結尾不存在*
else return 3; //如果前一區域的結尾存在*
}
}
int StarDealing(char *string,int position)
{
if(IsTransitionElement(string[position]))
return 1;
else
return 0;
}
Relation relation[25];
int relationi=0;
void ToNFA(char *string)
{
//Relation relation[25];
TokenState token[20];
int Rtoken[20];//記錄字符串中操作符號在操作符號列中的位置
int tokeni=1; //定義操作符號在操作符號中的位置
//int relationi=0;
int secondtoken;
token[0].BeginState=0;
token[0].EndState=0;
for (unsigned i=0;i<strlen(string);i++)
{
if (string[i]=='*')
{
Rtoken[i]=tokeni;
if (IsTransitionElement(string[i-1])) //處理型如“輸入字符 操作符*”
{
token[tokeni].BeginState=token[tokeni-1].EndState+1;
token[tokeni].EndState=token[tokeni].BeginState + 1;
token[tokeni].preposition = i-1;
NFADiagram(relation,relationi++,token[tokeni].BeginState,
token[tokeni].EndState ,string[i-1]);
// cout<<"5 ";
//對處理1*有問題。
NFADiagram(relation,relationi++,token[tokeni].EndState,
token[tokeni].BeginState , '$');
NFADiagram(relation,relationi++,token[tokeni].BeginState-1,
token[tokeni].EndState + 1 , '$');
NFADiagram(relation,relationi++,token[tokeni].BeginState-1,
token[tokeni].BeginState , '$');
NFADiagram(relation,relationi++,token[tokeni].EndState,
token[tokeni].EndState+1 , '$');
token[tokeni].BeginState = token[tokeni].BeginState-1;
token[tokeni].EndState=token[tokeni].EndState + 1;
}
else //處理型如 “操作符 操作符*”
{
token[tokeni].BeginState=token[tokeni-1].BeginState;
token[tokeni].EndState=token[tokeni-1].EndState;
token[tokeni].preposition=token[tokeni-1].preposition;
// cout<<"6 ";
NFADiagram(relation,relationi++,token[tokeni].EndState,
token[tokeni].BeginState , '$');
NFADiagram(relation,relationi++,token[tokeni-1].BeginState,
token[tokeni].EndState + 1 , '$');
NFADiagram(relation,relationi++,token[tokeni-1].BeginState,
token[tokeni].BeginState , '$');
NFADiagram(relation,relationi++,token[tokeni].EndState,
token[tokeni].EndState+1 , '$');
token[tokeni].BeginState = token[tokeni-1].BeginState;
token[tokeni].EndState=token[tokeni].EndState + 1;
}
tokeni++;
}
else if(string[i]=='+')
{
Rtoken[i]=tokeni;
switch(TokenDealing(string,i-1,token,Rtoken))
{
case 0: token[tokeni].BeginState=token[tokeni-1].EndState+1;
token[tokeni].EndState=token[tokeni].BeginState + 2;
token[tokeni].preposition=i-2;
NFADiagram(relation,relationi++,token[tokeni].BeginState,
token[tokeni].BeginState+1 , string[i-2]);
NFADiagram(relation,relationi++,token[tokeni].BeginState+1,
token[tokeni].EndState,string[i-1]);
// cout<<"1 ";
break;
//case 0:處理同10+類型即倆個輸入字符
case 1: token[tokeni].BeginState=token[tokeni-1].EndState;
token[tokeni].EndState=token[tokeni].BeginState + 1;
token[tokeni].preposition=token[tokeni-1].preposition;
NFADiagram(relation,relationi++,token[tokeni].BeginState,
token[tokeni].EndState , string[i-1]);
token[tokeni].BeginState=token[tokeni-1].BeginState; //對于整個區域而言 記錄可能存在的*操作的其實狀態，
// cout<<"2 ";
break;
//case 1:同1+類型即一個輸入字符
case 2:
token[tokeni].BeginState=token[tokeni-1].BeginState-1;
token[tokeni].EndState=token[tokeni-1].BeginState;
token[tokeni].preposition=token[tokeni-1].preposition-1;
NFADiagram(relation,relationi++,token[tokeni].BeginState,
token[tokeni].EndState , string[token[tokeni-1].preposition-1]);
token[tokeni].EndState=token[tokeni-1].EndState;
// cout<<"3 ";
break;
case 3: secondtoken=token[Rtoken[i-1]].preposition-1;
token[tokeni].BeginState=token[Rtoken[secondtoken]].EndState;
token[tokeni].EndState=token[tokeni-1].BeginState;
token[tokeni].preposition=token[secondtoken].preposition;
NFADiagram(relation,relationi++,token[tokeni].BeginState,
token[tokeni].EndState , '$');
token[tokeni].BeginState=token[Rtoken[secondtoken]].BeginState;
token[tokeni].EndState=token[tokeni-1].EndState;
// cout<<"4 ";
break;
}
tokeni++;
}
else if(string[i]=='|')
{
Rtoken[i]=tokeni;
switch(TokenDealing(string,i-1,token,Rtoken))
{
case 0: token[tokeni].BeginState=token[tokeni-1].EndState+1;
token[tokeni].EndState=token[tokeni].BeginState + 5;
token[tokeni].preposition=i-2;
NFADiagram(relation,relationi++,token[tokeni].BeginState,
token[tokeni].BeginState+1 , '$');
NFADiagram(relation,relationi++,token[tokeni].BeginState+1,
token[tokeni].BeginState+2 , string[i-2]);
NFADiagram(relation,relationi++,token[tokeni].BeginState,
token[tokeni].BeginState+3 , '$');
NFADiagram(relation,relationi++,token[tokeni].BeginState+3,
token[tokeni].BeginState+4 , string[i-1]);
NFADiagram(relation,relationi++,token[tokeni].BeginState+2,
token[tokeni].EndState , '$');
NFADiagram(relation,relationi++,token[tokeni].BeginState+4,
token[tokeni].EndState , '$');
// cout<<"7 ";
break;
//case 0:處理型如“輸入字符 輸入字符 |”
case 1: token[tokeni].BeginState=token[tokeni-1].BeginState-1;
token[tokeni].EndState=token[tokeni-1].EndState+3;
token[tokeni].preposition=token[tokeni-1].preposition;
NFADiagram(relation,relationi++,token[tokeni].BeginState,
token[tokeni].BeginState+1 , '$');
NFADiagram(relation,relationi++,token[tokeni].BeginState,
token[tokeni].EndState+1 , '$');
NFADiagram(relation,relationi++,token[tokeni].EndState+1,
token[tokeni].EndState+2 , string[i-1]);
NFADiagram(relation,relationi++,token[tokeni].EndState,
token[tokeni].EndState+3 , '$');
NFADiagram(relation,relationi++,token[tokeni].EndState+2,
token[tokeni].EndState+3 , '$');
// cout<<"8 ";
break;
//case 1:處理型如“+ 輸入字符 |”
case 2:token[tokeni].BeginState=token[tokeni-1].BeginState-1;
token[tokeni].EndState=token[tokeni-1].EndState+3;
token[tokeni].preposition=token[Rtoken[i-1]].preposition-1;
NFADiagram(relation,relationi++,token[tokeni].BeginState,
token[tokeni].BeginState+1 , '$');
NFADiagram(relation,relationi++,token[tokeni].BeginState,
token[tokeni].EndState-2 , '$');
NFADiagram(relation,relationi++,token[tokeni].EndState-2,
token[tokeni].EndState-1 , string[token[Rtoken[i-1]].preposition-1]);
NFADiagram(relation,relationi++,token[tokeni].EndState-1,
token[tokeni].EndState , '$');
NFADiagram(relation,relationi++,token[tokeni].EndState-3,
token[tokeni].EndState , '$');
// cout<<"9 ";
break;
//case 2:處理型如“+ |”
case 3:token[tokeni].EndState=token[tokeni-1].EndState+1;
secondtoken=token[Rtoken[i-1]].preposition-1;
//secondtoken指倆處理前一區域中的結束字符在波蘭式中位置
//token[tokeni].BeginState=token[Rtoken[secondtoken]].BeginState-1;
if(token[Rtoken[secondtoken]].BeginState!=0)
{ token[tokeni].BeginState=token[Rtoken[secondtoken]].BeginState-1;}
else if(token[Rtoken[secondtoken]].BeginState==0)
{ token[tokeni].BeginState=token[Rtoken[secondtoken]].BeginState;}
NFADiagram(relation,relationi++,token[tokeni].BeginState,
token[Rtoken[secondtoken]].BeginState, '$');
NFADiagram(relation,relationi++,token[tokeni].BeginState,
token[tokeni-1].BeginState , '$');
NFADiagram(relation,relationi++,token[tokeni-1].EndState,
token[tokeni].EndState , '$');
NFADiagram(relation,relationi++,token[Rtoken[secondtoken]].EndState,
token[tokeni].EndState , '$');
// cout<<"A ";
break;
//case 3:處理型如“+ |”
}
tokeni++;
}
}
int compare=10000;
for (int j=0;j<relationi;j++)
{
if(relation[j].CurrentState<compare)
compare=relation[j].CurrentState;
}
for (j=0;j<relationi;j++)
{
relation[j].CurrentState -= compare;
relation[j].NextState -= compare;
}
cout<<"****** 正則式=====>NFA ******"<<endl;
for (j=0;j<relationi;j++)
cout<<"從狀態: "<<relation[j].CurrentState<<" "
<<"到狀態 "<<relation[j].NextState<<" "
<<"輸入字符為 : "<<relation[j].TransitionElement<<endl;
}
void ToReversePolish(char *statement,char *ReversePolishString) //生成轉化字符串
{
int Si=0,top=0,RPSi=0;
char stack[15];
while(statement[Si]!='\0')
{
if (IsTransitionElement(statement[Si]))
{
if ((statement[Si-1]=='0' || statement[Si-1]=='1'
|| statement[Si-1] ==')' || statement[Si-1]=='$'
|| statement[Si-1] =='*') && Si-1>=0)
{
top--;
while((stack[top]=='+' || stack[top]=='*') && top>=0) //將操作符號往前移動
{
ReversePolishString[RPSi]=stack[top];
top--;
RPSi++;
}
top++;
stack[top]='+';
top++;
}
ReversePolishString[RPSi]=statement[Si];
RPSi++;
Si++;
}
else if (statement[Si]=='(')
{
if ((statement[Si-1]=='0' || statement[Si-1]==')'
|| statement[Si-1]=='1'||statement[Si-1]=='$'
|| statement[Si-1] =='*') && Si-1>=0)
{
top--;
while((stack[top]=='+' || stack[top]=='*') && top>=0)
{
ReversePolishString[RPSi]=stack[top];
top--;
RPSi++;
}
top++;
stack[top]='+';
top++;
}
stack[top]=statement[Si];
top++;
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -