正规表达式转NFA(C++)

分析

表达式里包含五种符号:左括号,右括号,连接符,选择符,闭包符。
连接符因为优先级最高,可以将其过滤掉,不予考虑。

闭包符*

首先来说闭包,无非两种情况:
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('#');
                s_st.push(s_ed.top());
                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