分析
表达式里包含五种符号：左括号，右括号，连接符，选择符，闭包符。
连接符因为优先级最高，可以将其过滤掉，不予考虑。
闭包符*
首先来说闭包，无非两种情况：
X* 或者 (…..)*
两者都可以看做是从一个起始状态，经过诸多输入到达一个终止状态。如 1– X –>2 和 1– (……) –> 2。
那么闭包符可以看做是以下操作：
1 – ε –> 2
2 – ε –> 1
即将首尾以空连接即可。
选择符|
把整体式也看做在一个大括号内的话，我们可以认为选择符一定是在括号内出现的。那么对一个括号内的表达式，我们给定它一个起始状态和终止状态，那么选择符处理方法如下：
(.A.|.B.|.C.)
st – .A. –> ed
st – .B. –> ed
st – .C. –> ed
即将|分隔的每部分表达式都与首尾状态连接。
括号()
因为括号的嵌套问题，让这个转化变得稍微棘手了些，但利用递归思想，每个括号里面的表达式看做一个子问题，对于括号内的式子给定该式一起始状态和终止状态，那么(…)和X也就没有什么区别了。
思路
首先我们定义三个栈：
s_str，保存输入信息
s_st，保存起始状态序号
s_ed，保存终止状态序号
我们用一个例子来解释栈的进出规则。
ab*(a*|(ab)*)
上式基本涵盖了所有表达式存在的情况，仔细看完它的转化过程，转化为代码是很容易的。
首先，将整个式子的起始状态id设为0和终止状态id为1，将其分别入栈s_st和s_ed
接下来对整个表达式进行扫描
[a] 添加状态id=3，入栈s_st，a入栈s_str.
[b] 添加状态id=4，入栈s_st，b入栈s_str.
[(] 因为上一个符号b已经添加的状态4可以作为括号内部分的起始状态，那么只添加终止状态=5，入栈s_ed，(入栈s_str.
[a] 添加状态id=6，入栈s_st，a入栈s_str.
[*] 获取s_st栈顶的两个状态，4和6, 添加4–ε–>6 和 6–ε–>4
[|] 依次对s_str进行出栈直到栈顶为(，同时对s_st进行出栈，
并将其两两用s_str进行连接. 如a出栈(s_str)，6出栈(s_st)，添加4–a–>6.
最重要的地方是，将最先出栈的状态id与s_ed进行连接，即添加 6–ε–>5.
[(] 添加终止状态=7，入栈s_ed，(入栈s_str.
[a] 添加状态id=8，入栈s_st，a入栈s_str.
[b] 添加状态id=9，入栈s_st，b入栈s_str.
[)] 依次对s_str进行出栈直到栈顶为(，同时对s_st进行出栈，
并将其两两用s_str进行连接(和|有些类似)，然后将该括号部分的终止id出栈=7，并将其入栈s_st，
同时入栈’-‘至s_str，’-‘作为括号里面部分式子的输入符号(其实是起占位符的作用，
这样的话，括号整体部分就与单个输入没有区别，既便于闭包符的处理，又解决了多个括号并列的情况).
[*] 获取s_st栈顶的两个状态，6和7, 添加7–ε–>6 和 6–ε–>7
[)] 与上面）的处理是完全一样的。
代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
struct Node
{
Node(int id, char input, int nextId)
{
this->id = id;
this->input = input;
this->nextId = nextId;
}
int id;
char input;
int nextId;
};
class MyClass
{
public:
MyClass() {
strExpress = "";
statusId = 0;
}
MyClass(string str)
{
strExpress = str;
}
void printNFA();
void strToNFA();
private:
string strExpress;
int statusId;
vector<Node*> map;
};
void MyClass::strToNFA()
{
stack<int> s_st;
stack<int> s_ed;
stack<char> s_str;
s_str.push('$');
s_st.push(statusId++);
s_ed.push(statusId++);
for(auto i=strExpress.begin(); i!=strExpress.end(); ++i)
{
char ch = *i;
cout<<ch;
switch (ch)
{
case '(':
{
s_ed.push(statusId++);
s_str.push('(');
break;
}
case ')':
{
int ed = s_ed.top();
int st = s_st.top();
map.push_back(new Node(st, '-', ed));
ch = s_str.top();
while(ch != '(')
{
int nxt = s_st.top();
s_st.pop();
int pre = s_st.top();
if(ch != '#')
map.push_back(new Node(pre, ch, nxt));
s_str.pop();
ch = s_str.top();
}
s_str.pop();
s_str.push('#');
int top_num = s_ed.top();
s_st.push(top_num);
s_ed.pop();
break;
}
case '|':
{
int ed = s_ed.top();
int st = s_st.top();
map.push_back(new Node(st, '-', ed));
ch = s_str.top();
while(ch != '(' && ch != '$')
{
int nxt = s_st.top();
s_st.pop();
int pre = s_st.top();
if(ch != '#')
map.push_back(new Node(pre, ch, nxt));
s_str.pop();
ch = s_str.top();
}
break;
}
case '*':
{
int nxt = s_st.top();
s_st.pop();
int pre = s_st.top();
map.push_back(new Node(pre, '-', nxt));
map.push_back(new Node(nxt, '-', pre));
s_st.push(nxt);
break;
}
default:
{
s_str.push(ch);
s_st.push(statusId++);
break;
}
}
}
char ch = s_str.top();
while(ch != '$')
{
int nxt = s_st.top();
s_st.pop();
int pre = s_st.top();
if(ch != '#')
map.push_back(new Node(pre, ch, nxt));
s_str.pop();
ch = s_str.top();
}
}
void MyClass::printNFA()
{
cout<<"NFA："<<endl;
for(auto node : map)
{
cout<<node->id<<"--["<<node->input<<"]-->"<<node->nextId<<endl;
}
}
int main()
{
string str;
stack<int> s;
// cin>>str;
str = "ab*(a*|(ab)*|b)*b";
MyClass myclass(str);
myclass.strToNFA();
myclass.printNFA();
return 0;
}
output
ab*(a*|(ab)*|b)*bNFA：
2--[-]-->3
3--[-]-->2
3--[-]-->5
5--[-]-->3
5--[-]-->4
3--[a]-->5
8--[-]-->6
7--[b]-->8
3--[a]-->7
3--[-]-->6
6--[-]-->3
6--[-]-->4
9--[-]-->4
3--[b]-->9
3--[-]-->4
4--[-]-->3
4--[b]-->10
2--[b]-->3
0--[a]-->2