c++ - 正则表达式算法

Question

我需要编写一个算法来确定单词 W 是否来自用正则表达式描述的语言 L。

例如:L = {a, b, c}*, RegEx = ab+c.a+(正则表达式以逆波兰表示法给出)，单词为ac 。在这里，我需要确定单词 ac 是否满足我们的正则表达式。

目前我只有在没有*的情况下才能解决这个问题。

这是我的代码:

void Recognize(string RegEx, string word) {
    string op1;
    bool iop1;
    string op2;
    bool iop2;
    stack <pair<string, bool>> st;
    int cnt = 0;
    for (int i = 0; i < regEx.size(); ++i) {
        string c = "";
        c.assign(1, regEx[i]);
        if (c == "." || c == "+" || c == "*") {
            if (c == ".") {
                op1 = st.top().first;
                iop1 = st.top().second;
                st.pop();
                op2 = st.top().first;
                iop2 = st.top().second;
                st.pop();
                if (iop1 == true && iop2 == true) {
                    st.push(make_pair(op1 + op2, true));
                }
                else {
                    st.push(make_pair(op1 + op2 + ".", false));
                }
            }
            if (c == "+") {
                op1 = st.top().first;
                iop1 = st.top().second;
                st.pop();
                op2 = st.top().first;
                iop2 = st.top().second;
                st.pop();
                if ((iop1 == true && iop2 == false) || (iop1 == false && iop2 == true)) {
                    st.push(make_pair(op1 + op2 + "+", true));
                }
                else {
                    st.push(make_pair(op1 + op2, false));
                }
            }
            if (c == "*") {
                // I have no idea what to do here.
            }
        }
        else {
            string temp;
            temp.assign(1, word[cnt]);
            if (c == temp) {
                st.push(make_pair(c, true));
                ++cnt;
                if (cnt == word.size()) {
                    cnt = 0;
                }
            }
            else {
                st.push(make_pair(c, false));
            }

        }
    }
    if (st.top().second == true) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

我对使用递归有一些想法，但我不确定。

谢谢。

Answer 1

如果你不想(或不能)使用标准库来处理正则表达式，你可以这样做:

1. 为此正则表达式构建一个 epsilon-NFA。

2. 移除 epsilon 转换。

3. 将此 NFA 转换为 DFA。

4. 遍历 DFA 并查看最终状态是否为终结状态。

如果构建 DFA 不可行，还有另一种方法:运行深度优先搜索。顶点是成对的(字符串前缀长度，NFA 中的状态)。边是 NFA 中的边。然后你需要检查一对(整个字符串长度，终端状态)对于至少一个终端状态是否可达。这种方法具有多项式空间和时间复杂度(因为 NFA 中的状态数是正则表达式长度的多项式)。