正则表达式算法

Question

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

例如：L = {a, b, c}*, RegEx = ab+c.a+ (regular expression is given in Reverse Polish notation)，单词为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中的状态数是正则长度的多项式）。