📄 regexptonfa.cpp
字号:
}
//获取表达式
void RegularExpToNFA::GetExpression()
{
char temp[40];
bool c;
int length=0;
cout<<"\n 请你输入一个正则表达式(字母表只包括0,1,e)";
do
{
cout<<"\n 表达式: ";
cin>>exp;
length = strlen(exp);
for (int i=0; i<length; i++)
{
if (exp[i]!='0' && exp[i]!='1' && exp[i]!='(' && exp[i]!=')' && exp[i]!='|' && exp[i]!='*' && exp[i]!='e' && exp[i]!='.')
{
cout << "\n 输入中包含错误的字符! 请重新输入" << endl;
c = true;
break;
}
else
c = false;
}
}while(c);
for(int i=0,j=0;i<length;i++,j++)
{
temp[j] = exp[i];
if (exp[i] == '0'||exp[i] == '1'||exp[i] == ')'||exp[i] == '*')
{
if (exp[i+1] == '0'||exp[i+1] == '1'||exp[i+1] == '(')
{
temp[j+1] = '.';
j++;
}
}
}
temp[j] = '\0';
strcpy(exp,temp);
cout<<"\n 你输入的正则表达式为：";
cout<<exp<<endl;
}
//定义symbol的优先级
int RegularExpToNFA::Precedence(char symbol)
{
int priority;
switch (symbol)
{
case '|': priority = 1; break;
case '.': priority = 2; break;
case '*': priority = 3; break;
default: priority = 0; break;
}
return priority;
}
// 将正则式转为后缀表达式
void RegularExpToNFA::ExpToPostFix()
{
int i = 0, j = 0;
char ch, cl;
stack<char> *st = new stack<char>(0);
strcpy(post, "\0");
st->clear();
st->push('#');
ch = exp[i];
//转化过程
while (ch != '\0')
{
if (ch == '(')
{
st->push(ch);
ch = exp[++i];
}
else if (ch == ')')
{
while ( st->GetTop()!= '(')
{
post[j++] = st->pop();
}
st->pop();
ch = exp[++i];
}
else if ((ch == '|') || (ch == '*') || (ch == '.'))
{
cl = st->GetTop();
while (Precedence(cl) >= Precedence(ch))
{
post[j++] = cl;
st->pop();
cl = st->GetTop();
}
st->push(ch);
ch = exp[++i];
}
else if ((ch == '0') || (ch == '1') || (ch == 'e'))
{
post[j++] = ch;
ch = exp[++i];
}
}
ch = st->pop();
while ((ch == '|') || (ch == '*') || (ch == '.'))
{
post[j++] = ch;
ch = st->pop();
}
post[j] = '\0';
st->clear();
cout<<"\n 正则式转为后缀表达式式为：";
cout<< post <<endl;
}/*
void RegularExpToNFA::Compute()
{
int i = 0;
st = new stack<char>(0);
st->clear();
st->push('#');
ss = new stack<int>(0);
ss->clear();
while (post[i]!='\0')
{
switch (post[i])
{
case '1': case '0': case 'e':
st->push(post[i]);
break;
case '|': case '*': case '.':
FormNFA(post[i]);
break;
default:
break;
}
}
}
//NFA子结构的生成
void RegularExpToNFA::FormNFA(char op)
{
int i=0,j=0,count = 0 ;
char left,right;
bool flag = true;
if (st->IsEmpty())
{
cout<<"\n 栈已空!";
flag = false;
}
right = st->pop();
if (st->IsEmpty())
{
cout<<"\n 栈已空!";
flag = false;
}
left = st->pop();
if (flag)
{
switch (op)
{
case '*':
break;
case '|':
break;
case '.':
break;
default:
break;
}
}
else
st->clear();
}*/
// 用Thompson法构造NFA
int RegularExpToNFA::ThompsonMethod()
{
int i=0, len = strlen(post);
char ch;
int s1, s2;
stack<char> *ls = new stack<char>(0);
stack<int> *state = new stack<int>(0);
ls->clear();
ls->push('#');
state->clear();
if (len < 0)
{
cerr << "No Valid Regular Expression Found!" << endl;
getch();
exit(1);
}
for (i=len-1; i>=0; i--)
{
ls->push(post[i]);
}
table->SetValue(0, 0);
i = 1;
ch = ls->pop();
while (1)
{
if ((ch == '0') || (ch == '1') || (ch == 'e'))
{
table->InsertVertex(i);
table->InsertVertex(i+1);
table->InsertEdgeByValue(i, i+1, ch);
s1 = i;
s2 = i+1;
state->push(s1);
state->push(s2);
i += 2;
}
else if (ch == '.')
{
s2 = state->pop();
int temp1 = state->pop();
int temp2 = state->pop();
s1 = state->pop();
table->InsertEdgeByValue(temp2, temp1, 'e');
state->push(s1);
state->push(s2);
}
else if (ch == '|')
{
s2 = state->pop();
int temp1 = state->pop();
int temp2 = state->pop();
s1 = state->pop();
table->InsertVertex(i);
table->InsertVertex(i+1);
table->InsertEdgeByValue(i, s1, 'e');
table->InsertEdgeByValue(i, temp1, 'e');
table->InsertEdgeByValue(temp2, i+1, 'e');
table->InsertEdgeByValue(s2, i+1, 'e');
s1 = i;
s2 = i+1;
state->push(s1);
state->push(s2);
i += 2;
}
else if (ch == '*')
{
s2 = state->pop();
s1 = state->pop();
table->InsertVertex(i);
table->InsertVertex(i+1);
table->InsertEdgeByValue(i, i+1, 'e');
table->InsertEdgeByValue(s2, s1, 'e');
table->InsertEdgeByValue(i, s1, 'e');
table->InsertEdgeByValue(s2, i+1, 'e');
s1 = i;
s2 = i+1;
state->push(s1);
state->push(s2);
i += 2;
}
ch = ls->pop();
if (ch == '#')
{
break;
}
}
s2 = state->pop();
s1 = state->pop();
table->InsertEdgeByValue(0, s1, 'e');
ls->clear();
state->clear();
return s2;
}
// 用邻接表形式输出构造的NFA
void RegularExpToNFA::OutputNFA(int end)
{
int len = strlen(post);
cout<<"\n ━━━━━━━━━━━━━━━━━━━━";
cout<<"\n 下面是从正则表达式转化成的 NFA ：";
cout<<"\n 1. 字 母 表："<<"0, 1";
cout<<"\n 2. 状 态 集：";
for (int i=0;i<table->GetVertexNumber();i++)
{
cout<<i<<",";
}
cout<<'\b';
cout<<"\n 3. 初始 状态：0";
cout<<"\n 4. 接收状态集：";
cout<<end;
for(i=0;i<0;i++)
{
cout<<endState[i]<<",";
}
cout<<"\n 5. 转化函数表：\n";
cout<<"\n ━━━┯━━━━━━━━━━━━━━━━";
cout<<"\n │ 输入字母 ";
cout<<"\n 状态 ┝━━━━┯━━━━━┯━━━━━";
cout<<"\n │ 0 │ 1 │ e";
cout<<"\n ━━━┿━━━━┿━━━━━┿━━━━━";
cout<<endl;
table->Output();
cout<<endl;
table->Clear();
}
//整个处理总流程
void RegularExpToNFA::Run()
{
//输入表达式
GetExpression();
//将正则式转为后缀表达式
ExpToPostFix();
// 用Thompson法构造NFA并返回接收状态
int end = ThompsonMethod();
// 用邻接表形式输出NFA
OutputNFA(end);
}
///////////////////////////
//Main Function
void main()
{
RegularExpToNFA con;
con.Run();
cout<<"\n 按任意键退出....";
cout<<endl;
getch();
}
/////////////////////////////////////////
/*/下面是测试的正则表达式(0或1)和结果
（1）1(01|1) 输出的结果如下：
请你输入一个正则表达式(字母表只包括0,1,e)
表达式: 1(01|1)
你输入的正则表达式为：1.(0.1|1)
正则式转为后缀表达式式为：101.1|.
━━━━━━━━━━━━━━━━━━━━
下面是从正则表达式转化成的 NFA ：
1. 字 母 表：0, 1
2. 状 态 集：0,1,2,3,4,5,6,7,8,9,10,
3. 初始 状态：0
4. 接收状态集：10
5. 转化函数表：
━━━┯━━━━━━━━━━━━━━━━
│ 输入字母
状态 ┝━━━━┯━━━━━┯━━━━━
│ 0 │ 1 │ e
━━━┿━━━━┿━━━━━┿━━━━━
0 │ -- │ -- │ 1
1 │ -- │ 2 │ --
2 │ -- │ -- │ 9
3 │ 4 │ -- │ --
4 │ -- │ -- │ 5
5 │ -- │ 6 │ --
6 │ -- │ -- │ 10
7 │ -- │ 8 │ --
8 │ -- │ -- │ 10
9 │ -- │ -- │ 3 7
10 │ end │ -- │ --
按任意键退出....
（2）1(01|1)* 输出的结果如下：
请你输入一个正则表达式(字母表只包括0,1,e)
表达式: 1(01|1)*
你输入的正则表达式为：1.(0.1|1)*
正则式转为后缀表达式式为：101.1|*.
━━━━━━━━━━━━━━━━━━━━
下面是从正则表达式转化成的 NFA ：
1. 字 母 表：0, 1
2. 状 态 集：0,1,2,3,4,5,6,7,8,9,10,11,12,
3. 初始 状态：0
4. 接收状态集：12
5. 转化函数表：
━━━┯━━━━━━━━━━━━━━━━
│ 输入字母
状态 ┝━━━━┯━━━━━┯━━━━━
│ 0 │ 1 │ e
━━━┿━━━━┿━━━━━┿━━━━━
0 │ -- │ -- │ 1
1 │ -- │ 2 │ --
2 │ -- │ -- │ 11
3 │ 4 │ -- │ --
4 │ -- │ -- │ 5
5 │ -- │ 6 │ --
6 │ -- │ -- │ 10
7 │ -- │ 8 │ --
8 │ -- │ -- │ 10
9 │ -- │ -- │ 3 7
10 │ -- │ -- │ 9 12
11 │ -- │ -- │ 12 9
12 │ end │ -- │ --
按任意键退出....
（3） 1(01|1)*|1*00 输出的结果如下：
请你输入一个正则表达式(字母表只包括0,1,e)
表达式: 1(01|1)*|1*00
你输入的正则表达式为：1.(0.1|1)*|1*.0.0
正则式转为后缀表达式式为：101.1|*.1*0.0.|
━━━━━━━━━━━━━━━━━━━━
下面是从正则表达式转化成的 NFA ：
1. 字 母 表：0, 1
2. 状 态 集：0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
3. 初始 状态：0
4. 接收状态集：22
5. 转化函数表：
━━━┯━━━━━━━━━━━━━━━━
│ 输入字母
状态 ┝━━━━┯━━━━━┯━━━━━
│ 0 │ 1 │ e
━━━┿━━━━┿━━━━━┿━━━━━
0 │ -- │ -- │ 21
1 │ -- │ 2 │ --
2 │ -- │ -- │ 11
3 │ 4 │ -- │ --
4 │ -- │ -- │ 5
5 │ -- │ 6 │ --
6 │ -- │ -- │ 10
7 │ -- │ 8 │ --
8 │ -- │ -- │ 10
9 │ -- │ -- │ 3 7
10 │ -- │ -- │ 9 12
11 │ -- │ -- │ 12 9
12 │ -- │ -- │ 22
13 │ -- │ 14 │ --
14 │ -- │ -- │ 13 16
15 │ -- │ -- │ 16 13
16 │ -- │ -- │ 17
17 │ 18 │ -- │ --
18 │ -- │ -- │ 19
19 │ 20 │ -- │ --
20 │ -- │ -- │ 22
21 │ -- │ -- │ 1 15
22 │ end │ -- │ --
按任意键退出....
/////////////////////////////////////////*/ ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -