Morris' Blog

2014-03-14 22:17:48Morris

[編譯器][C/C++] simple regex to NFA

留言 0 收藏 0 推薦 0
請參考 http://mypaper.pchome.com.tw/zerojudge/post/1324174148

Input format:

輸入只會有一筆 NFA 描述，輸入以 EOF(end-of-file) 為結尾。

輸入第一行為字母集(set of input symbols Σ)，表示方法為 "(c1, c2, … cn, size)"。其中 ci 為 ASCII [32, 127] 的可視字符，其中特別以 'l' 字符表示 lambda。size(size = n-1)則為字母集的大小。

接下來會有數行表示每一個狀態的轉移，每一行上會有 n 個集合以 ‘(’ 和 ‘)’ 做為區隔，每個集合中會用逗號(‘,’)區隔每一個狀態編號。對於第 i 行的第 j 個集合 s(i, j)，表示 statei 可以藉由 cj 轉移到 s(i, j) 中任意狀態。

若第 i 行上的集合出現 ‘*’，表示 statei 是一個 accepting state Fi。特別以 state1 作為 start state。

(1 <= i <= m, 1 <= j <= n < size)

Output format:

輸出一組 DFA，格式如下。
輸出第一行為字母集 CDFA (按照字典順序輸出)。

接下來會有輸出 m 行，每行上表示每一個狀態的轉移，第一個集合為對應原本 NFA 的元素集合，接下來會有 CDFA.size() 個狀態，每個狀態皆以集合的方式呈現。對於第 i 行的第 j+1 個狀態 statej，表示 statei 可以藉由 CDFA[j] 轉移到 statej。

並且對應 NFA 的元素集合，採用最小字典順序的方式輸出(即排序後輸出)，若該狀態可以被 accepted，則使用一個 ‘*’ 放到狀態最前面輸出。

請參考範例輸入輸出。

為了方便起見，這個程式用來讀入一個簡單的正規表達式並且轉成指定的 NFA Table (格式如上)。

simple regex 是只由 a-z 構成主要字符，能當作 operator 的只有 '(', ')', '|', '*'

寫的方式還正在想辦法改進，對於每一個狀態都是一個指標來儲存，用來方便串接 NFA 的狀態複製，但這樣的情況會造成，想要複製 NFA 的時候，對於每一個狀態並不是真的複製，整個程式在運行時，每個狀態皆會一直保留，忘了著手 free() 和 clone() ...

Sample Input

(a|b)*a
(a|b)*bb
(b)*(ab(b)*)*b
(aaaa|b)*
a*((ba)*baa)*b*

Sample Output

(l,a,b)
(2,3)(0)(0)
(4,5)(0)(0)
(6)(0)(0)
(0)(7)(0)
(0)(0)(8)
(0)(9)(0)
(10)(0)(0)
(10)(0)(0)
(*)(*)(*)
(2,3)(0)(0)

(l,a,b)
(2,3)(0)(0)
(4,5)(0)(0)
(6)(0)(0)
(0)(7)(0)
(0)(0)(8)
(0)(0)(9)
(10)(0)(0)
(10)(0)(0)
(0)(0)(11)
(2,3)(0)(0)
(*)(*)(*)

(l,a,b)
(2,3)(0)(0)
(0)(0)(4)
(5)(0)(0)
(2,3)(0)(0)
(6,7)(0)(0)
(0)(8)(0)
(9)(0)(0)
(0)(0)(10)
(0)(0)(11)
(12)(0)(0)
(*)(*)(*)
(13,14)(0)(0)
(0)(0)(15)
(6,7)(0)(0)
(13,14)(0)(0)

(l,a,b)
(2,3)(0)(0)
(4,5)(0)(0)
(*)(*)(*)
(0)(6)(0)
(0)(0)(7)
(0)(8)(0)
(9)(0)(0)
(0)(10)(0)
(2,3)(0)(0)
(0)(11)(0)
(9)(0)(0)

(l,a,b)
(2,3)(0)(0)
(0)(4)(0)
(5)(0)(0)
(2,3)(0)(0)
(6,7)(0)(0)
(8,9)(0)(0)
(10)(0)(0)
(0)(0)(11)
(12)(0)(0)
(13,14)(0)(0)
(0)(15)(0)
(0)(0)(16)
(0)(0)(17)
(*)(*)(*)
(8,9)(0)(0)
(0)(18)(0)
(13,14)(0)(0)
(0)(19)(0)
(6,7)(0)(0)

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
class State {
    public:
        State(int ac=0) {
            accepted = ac;
        }
        bool accepted;
        int nameLabel;
        map<char, vector<State*> > trans;
};
class DFA {
    public:
        State* Q0;
        vector<State*> Q, F;
};
class NFA {
    public:
        static char lambda;
        State* Q0;
        vector<State*> Q;
        vector<State*> F;
        vector< vector<State*> > make_deterministic(DFA &M, vector<char> alpha);
        static NFA getNFAbyString(const char str[]);
        static NFA getNFA_Star(NFA nfa);
        static NFA getNFA_OR(NFA n1, NFA n2);
        static NFA getNFA_AND(NFA n1, NFA n2);
        void print();
        void printTable();
        void buildLabel();
    private:
        vector<State*> getSetOf(vector<State*> set_of_states, char c);
        vector<State*> getClose(vector<State*> set_of_states);
};
char NFA::lambda = 0;
vector<State*> NFA::getSetOf(vector<State*> set_of_states, char c) {
    set<State*> h;
    vector<State*> ret;
    queue<State*> q;
    State* index;
    for(int i = 0; i < set_of_states.size(); i++) {
        index = set_of_states[i];
        q.push(index);
    }
    while(!q.empty()) {
        index = q.front(), q.pop();
        vector<State*> state_trans = index->trans[c];
        for(int i = 0; i < state_trans.size(); i++) {
            if(h.find(state_trans[i]) == h.end()) {
                h.insert(state_trans[i]);
                ret.push_back(state_trans[i]);
            }
        }
    }
    return ret;
}
/*
 * Add to S all states reachable from it
 * using only lembda transitions of N
 */
vector<State*> NFA::getClose(vector<State*> set_of_states) {
    set<State*> h;
    vector<State*> ret;
    queue<State*> q;
    State* index;
    for(int i = 0; i < set_of_states.size(); i++) {
        index = set_of_states[i];
        q.push(index), h.insert(index);
    }
    while(!q.empty()) {
        index = q.front(), q.pop();
        ret.push_back(index);
        vector<State*> state_trans = index->trans[NFA::lambda];
        for(int i = 0; i < state_trans.size(); i++) {
            if(h.find(state_trans[i]) == h.end()) {
                h.insert(state_trans[i]);
                q.push(state_trans[i]);
            }
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}
vector< vector<State*> > NFA::make_deterministic(DFA &M, vector<char> alpha) {
    vector< vector<State*> > T;
    vector<State*> stateSet;
    stateSet.push_back(Q0);
    vector<State*> init_state = getClose(stateSet);
    T.push_back(init_state);
    M.Q.push_back(new State());
    for(int i = 0; i < T.size(); i++) {
        State* state = M.Q[i];
        for(int j = 0; j < T[i].size(); j++)
            if(T[i][j]->accepted)
                state->accepted = 1;
        state->nameLabel = i;
        if(state->accepted)    M.F.push_back(state);
        for(int j = 0; j < alpha.size(); j++) {
            if(alpha[j] == NFA::lambda)
                continue;
            vector<State*> next_state = getSetOf(T[i], alpha[j]);
            next_state = getClose(next_state);
            int existIdx = -1;
            for(int k = 0; k < T.size(); k++) {
                if(T[k] == next_state) {
                    existIdx = k;
                    break;
                }
            }
            if(existIdx < 0) {
                T.push_back(next_state);
                M.Q.push_back(new State());
                existIdx = T.size()-1;
            }
            M.Q[i]->trans[alpha[j]].push_back(M.Q[existIdx]);
        }
    }
    M.Q0 = M.Q[0];
    return T;
}

NFA NFA::getNFAbyString(const char str[]) {
    NFA ret;
    ret.Q.push_back(new State());
    ret.Q0 = ret.Q[0];
    for(int i = 0; str[i]; i++) {
        ret.Q.push_back(new State());
        ret.Q[i]->trans[str[i]].push_back(ret.Q[i+1]);
    }
    ret.Q[ret.Q.size()-1]->accepted = 1;
    ret.F.push_back(ret.Q[ret.Q.size()-1]);
    return ret;
}

NFA NFA::getNFA_Star(NFA nfa) {
    State *s1, *s2;
    s1 = new State();
    s2 = new State(true);
    for(int i = 0; i < nfa.F.size(); i++) {
        nfa.F[i]->accepted = 0;
        nfa.F[i]->trans[NFA::lambda].push_back(s2);
        nfa.F[i]->trans[NFA::lambda].push_back(nfa.Q0);
    }
    s1->trans[NFA::lambda].push_back(nfa.Q0);
    s1->trans[NFA::lambda].push_back(s2);
    nfa.F.clear();
    nfa.F.push_back(s2);
    nfa.Q.push_back(s1);
    nfa.Q.push_back(s2);
    nfa.Q0 = s1;
    return nfa;
}

NFA NFA::getNFA_OR(NFA n1, NFA n2) {
    State *s1, *s2;
    s1 = new State();
    s2 = new State(true);
    s1->trans[NFA::lambda].push_back(n1.Q0);
    s1->trans[NFA::lambda].push_back(n2.Q0);
    for(int i = 0; i < n1.F.size(); i++) {
        n1.F[i]->accepted = 0;
        n1.F[i]->trans[NFA::lambda].push_back(s2);
    }
    n1.F.clear();
    for(int i = 0; i < n2.F.size(); i++) {
        n2.F[i]->accepted = 0;
        n2.F[i]->trans[NFA::lambda].push_back(s2);
    }
    for(int i = 0; i < n2.Q.size(); i++)
        n1.Q.push_back(n2.Q[i]);
    n1.F.push_back(s2);
    n1.Q.push_back(s1);
    n1.Q.push_back(s2);
    n1.Q0 = s1;
    return n1;
}
NFA NFA::getNFA_AND(NFA n1, NFA n2) {
    for(int i = 0; i < n1.F.size(); i++) {
        n1.F[i]->accepted = 0;
        n1.F[i]->trans[NFA::lambda].push_back(n2.Q0);
    }
    n1.F.clear();
    for(int i = 0; i < n2.F.size(); i++)
        n1.F.push_back(n2.F[i]);
    for(int i = 0; i < n2.Q.size(); i++)
        n1.Q.push_back(n2.Q[i]);
    return n1;
}
bool cmp(const State* a, const State* b) {
    return a->nameLabel < b->nameLabel;
}
void NFA::print() {
    printf("start[%d]\n", Q0->nameLabel);
    for(int i = 0; i < F.size(); i++) {
        printf("F[%d]", F[i]->nameLabel);
    }
    puts("");
    sort(Q.begin(), Q.end(), cmp);
    for(int i = 0; i < Q.size(); i++) {
        printf("Q[%d] : ", Q[i]->nameLabel);
        for(map<char, vector<State*> >::iterator it = Q[i]->trans.begin();
            it != Q[i]->trans.end(); it++) {
            printf("[%c,", it->first == 0 ? '~' : it->first);
            for(vector<State*>::iterator jt = it->second.begin();
                jt != it->second.end(); jt++) {
                printf(" %d", (*jt)->nameLabel);
            }
            printf("]");
        }
        puts("");
    }
}
void NFA::printTable() {
    set<char> alpha;
    sort(Q.begin(), Q.end(), cmp);
    for(int i = 0; i < Q.size(); i++) {
        for(map<char, vector<State*> >::iterator it = Q[i]->trans.begin();
            it != Q[i]->trans.end(); it++) {
            alpha.insert(it->first);
        }
    }
    for(set<char>::iterator it = alpha.begin(); it != alpha.end(); it++) {
        putchar(it == alpha.begin() ? '(' : ',');
        if(*it == NFA::lambda)    printf("l");
        else                    printf("%c", *it);
    }
    puts(")");
    for(int i = 0; i < Q.size(); i++) {
        for(set<char>::iterator it = alpha.begin();
            it != alpha.end(); it++) {
            vector<State*> &v = Q[i]->trans[*it];
            if(v.size() == 0)
                printf(Q[i]->accepted ? "(*)" : "(0)");
            else {
                printf("(%s", Q[i]->accepted ? "*" : "");
                sort(v.begin(), v.end(), cmp);
                for(int j = 0; j < v.size(); j++) {
                    printf("%d%c", v[j]->nameLabel+1, j == v.size()-1 ? ')' : ',');
                }
            }
        }
        puts("");
    }
}

void NFA::buildLabel() {
    set<State*> R;
    queue<State*> Q;
    int labelIdx = 0;
    Q.push(Q0), R.insert(Q0);
    while(!Q.empty()) {
        State* node = Q.front();
        Q.pop();
        node->nameLabel = labelIdx++;
        for(map<char, vector<State*> >::iterator it = node->trans.begin();
            it != node->trans.end(); it++) {
            for(vector<State*>::iterator jt = it->second.begin();
                jt != it->second.end(); jt++) {
                if(R.find(*jt) == R.end()) {
                    R.insert(*jt);
                    Q.push(*jt);
                }
            }
        }
    }
}
int priority_op(char c) {
    switch(c) {
        case '(':return 0;
        case '*':return 1;
        case '|':case '+':return 2;
    }
    return -1;
}
void trans(char infix[], char buffer[]) {
    int len = strlen(infix);
    char *ptr = buffer;
    stack<char> op;
    stack<int> elem;
    elem.push(0);
    *ptr = '\0';
    for(int i = 0; i < len; i++) {
        if(infix[i] >= 'a' && infix[i] <= 'z') {
            while(!op.empty() && op.top() == '*') {
                sprintf(ptr, "* ", op.top()), op.pop();
                while(*ptr)    ptr++;
            }
            while(infix[i] >= 'a' && infix[i] <= 'z' && i < len) {
                sprintf(ptr, "%c", infix[i]);
                while(*ptr)    ptr++;
                i++;
            }
            i--;
            sprintf(ptr, " ");
            while(*ptr)    ptr++;
            elem.top()++;
        }else {
            if(infix[i] == ')') {
                while(!op.empty() && op.top() != '(') {
                    if(op.top() == '|')    elem.top()--;
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                while(elem.top() > 1) {
                    sprintf(ptr, "+ ");
                    while(*ptr) ptr++;
                    elem.top()--;
                }
                elem.pop();
                elem.top()++;
                op.pop();
            } else {
                if(infix[i] != '(') {
                    while(!op.empty() && priority_op(op.top()) >= priority_op(infix[i])) {
                        sprintf(ptr, "%c ", op.top()), op.pop();
                        while(*ptr) ptr++;
                    }
                } else {
                    while(!op.empty() && op.top() == '*') {
                        sprintf(ptr, "* ", op.top()), op.pop();
                        while(*ptr)    ptr++;
                    }
                    elem.push(0);
                }
                op.push(infix[i]);
            }
        }
    }
    while(!op.empty()) {
        sprintf(ptr, "%c ", op.top()), op.pop();
        while(*ptr) ptr++;
    }
    while(elem.top() > 1) {
        sprintf(ptr, "+ ");
        while(*ptr) ptr++;
        elem.top()--;
    }
    elem.pop();
}
NFA calcPostfix(char postfix[]) {
    int len = strlen(postfix);
    stack<NFA> stk;
    stringstream sin(postfix);
    string token;
    while(sin >> token) {
        if(token[0] == '*') {
            NFA a;
            a = stk.top(), stk.pop();
            stk.push(NFA::getNFA_Star(a));
        } else if(token[0] == '|' || token[0] == '+') {
            NFA a, b;
            b = stk.top(), stk.pop();
            a = stk.top(), stk.pop();
            switch(token[0]) {
                case '|':stk.push(NFA::getNFA_OR(a, b));break;
                case '+':stk.push(NFA::getNFA_AND(a, b));break;
            }
        } else {
            stk.push(NFA::getNFAbyString(token.c_str()));
        }
    }
    return stk.top();
}
int main() {
    char s[1024], postfix[1024];
    while(scanf("%s", s) == 1) {
        trans(s, postfix);
        // puts(postfix);
        NFA ret = calcPostfix(postfix);
        ret.buildLabel();
        ret.printTable();
    }
    return 0;
}
/*
// strings ending with a
(a|b)*a
// strings ending with bb
(a|b)*bb
// strings ending with b and not containing aa
(b)*(ab(b)*)*b

(aaaa|b)*

a*((ba)*baa)*b*

an(ba)*bn

*/

上一篇：[其他題目][求助][未解] 折價購買最大量

你可能感興趣的文章

修行不要加油添醋

以下為一有緣人分享：   有位朋友，他們家常被無形眾生干擾，他自己也是敏感體質，到處求助無門。看到他的狀況，我跟他推薦了

14 小時前

夏日荷香

紅白蓮 　　宋 楊萬里 　　紅白蓮花開共塘， 　　兩般顏色一般香。 　　恰似漢殿三千女， 　　半是濃妝半淡妝。  

8 小時前

នៅក្នុងឧទ្យានអ្នកអាចជ្រើសរើសមួយក្នុងចំណោមពីរ

1ª ជ្រើសរើសបដិសេធព្រះយេស៊ូវដោយមិនមានការបៀតបៀន។ 2ª អ្នក​ណា​ដែ

2 小時前

2024.05.30

2024.5.30 台北 Ashley Johnson - Take On Me

2024-05-30

22機艦擾台 距鵝鑾鼻僅44浬 國防部預告中共將發射火箭經我ADIZ

https://www.msn.com/zh-tw/news/national/22%E6%A9%9F%E8%89%A6%E6%93%BE%E5%8F%B0-%E8%B7%9D%E9%B5%9D%E9%91%BE%E9%BC%BB%E5%83%85

2024-05-30
PChome首頁 線上購物 24h購物 書店 露天拍賣 商店街 比比昂代購
新聞 / 氣象 股市 個人新聞台 廣告刊登 加入聯播網 全球購物
泰國跨境 買賣租屋 支付連 國際連 Pi 拍錢包 旅遊 Skype Lingvist 服務中心
買車 旅行團 汽車險推薦 線上麻將 雜誌 星座命理 會員中心
一元簡訊 直播達人 數位憑證 企業簡訊
買網址 虛擬主機 企業郵件
廣告刊登 隱私權聲明
消費者保護 兒童網路安全
About PChome 投資人聯絡 徵才
著作權保護｜網路家庭版權所有、轉載必究 ‧Copyright PChome Online

PChome Online and PChome are trademarks of PChome Online Inc.