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

*/

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

你可能感興趣的文章

當代中文3-8：我想做自己 (學習單)

一、對話 (一)、口述內容大意 請簡述對話內容的主要情節與人物的困擾。（約50-100字） 對話圍繞三位人物的生活與困擾展開：李文彥

17 小時前

銅鑼生活第200週之3(2024/11/17)

星期六早上，我從銅鑼開車到東勢上班。   星期六上班，心情已經很不美麗了，下班前又發生一些狀況，當病人平安走出洗腎室時，

5 小時前

東京巨蛋初體驗

雖然我的最愛是籃球，但棒球是我們的國球，尤其是住在kano的發源地嘉義，怎麼說都不能無視棒球。 日本統治時代，由日本教練組成的

2 小時前

晚安小雞

            

2024-11-24

踏足主流社會，第24天

https://hearty.me/trigoamor180/1195159

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

PChome Online and PChome are trademarks of PChome Online Inc.