NFA using digraph

bfs.hpp

#ifndef bfs_hpp
#define bfs_hpp
#include "digraph.hpp"
#include "queue.hpp"

class BFS {
    private:
        bool *seen;
        int  *pred;
        void init(Digraph& G) {
            seen = new bool[G.V()];
            pred = new int[G.V()];
            for (int i = 0; i < G.V(); i++) {
                seen[i] = false;
                pred[i] = -1;
            }
        }
        void search(Digraph& G, int start) {
            Queue<int> fq;
            fq.push(start);
            seen[start] = true;
            pred[start] = start;
            while (!fq.empty()) {
                int curr = fq.pop();
                for (Edge u : G.adj(curr)) {
                    if (!seen[u.to]) {
                        seen[u.to] = true;
                        pred[u.to] = curr;
                        fq.push(u.to);
                    }
                }
            }
        }
    public:
        BFS(Digraph& G, int s) {
            init(G);
            search(G, s);
        }
        BFS(Digraph& G, Bag<int>& s) {
            init(G);
            for (int u : s)
                if (!seen[u])
                    search(G, u);
        }
        bool marked(int v) {
            return seen[v];
        }
};

#endif

nfa.hpp

#ifndef nfa_hpp
#define nfa_hpp
#include <iostream>
#include "digraph.hpp"
#include "bag.hpp"
#include "stack.hpp"
#include "bfs.hpp"
using namespace std;

class NFA {
    private:
        string re;
        int m;
        Digraph g;
        void buildTransitionGraph();
    public:
        NFA(string pattern);
        bool match(string text);
        void showNFA();
};

NFA::NFA(string pattern) {
    re = pattern;
    m = re.length();
    g = Digraph(m+1);
    buildTransitionGraph();
}

void NFA::buildTransitionGraph() {
    Stack<int> ops;
    for (int i = 0; i < re.length(); i++) {
        int lp = i;
        if (re[i] == '(' || re[i] == '|') {
            ops.push(i);
        } else if (re[i] == ')') {
            int ro = ops.pop();
            if (re[ro] == '|') {
                lp = ops.pop();
                g.addEdge(lp, ro+1);
                g.addEdge(ro, i);
            } else  if (re[ro] == '(') lp = ro;
        }
        if (i < m-1 && re[i+1] == '*') {
            g.addEdge(lp, i+1);
            g.addEdge(i+1, lp);
        }
        if (re[i] == '(' || re[i] == '*' || re[i] == ')')
            g.addEdge(i, i+1);
    }
    if (!ops.empty())
        cout<<"Something went wrong."<<endl;
}

bool NFA::match(string text) {
    Bag<int> pc;
    BFS dfs(g, 0);
    for (int v = 0; v < g.V(); v++) {
        if (dfs.marked(v))
            pc.add(v);
    }
    for (int i = 0; i < text.length(); i++) {
        Bag<int> states;
        for (int v : pc) {
            if (v == m) continue;
            if (re[v] == text[i] || re[v] == '.') {
                states.add(v+1);
            }
        }
        if (states.empty()) {
            continue;
        }
        dfs = BFS(g, states);
        pc.clear();
        for (int v = 0; v < g.V(); v++) {
            if (dfs.marked(v)) {
                pc.add(v);
            }
        }
        if (pc.empty()) {
            return false;
        }
    }
    for (int v : pc) 
        if (v == m) 
            return true;
    return false;
}

void NFA::showNFA() {
    for (int i = 0; i < m; i++) {
        cout<<i<<"("<<re[i]<<"): ";
        for (auto e : g.adj(i)) {
            cout<<e.to<<"("<<re[e.to]<<") ";
        }
        cout<<endl;
    }
}

#endif

queue.hpp

#ifndef queue_hpp
#define queue_hpp

template <class T>
class Queue {
    private:
        struct node {
            T info;
            node* next;
            node(T i) : info(i), next(nullptr) { }
        };
        node* head;
        node* tail;
        int count;
        void copy(const Queue& q) {
            clear();
            init();
            for (node* t = q.head; t != nullptr; t = t->next)
                push(t->info);
        }
        void init() {
            count = 0;
            head = nullptr;
            tail = nullptr;
        }
    public:
        Queue() {
            init();
        }
        Queue(const Queue& q) {
            copy(q);
        }
        int size() {
            return count;
        }
        bool empty() {
            return head == nullptr;
        }
        void push(T info) {
            node* t = new node(info);
            if (empty()) {
                head = t;
            } else {
                tail->next = t;
            }
            tail = t;
            count++;
        }
        T& front() {
            return head->info;
        }
        T pop() {
            T ret = head->info;
            node* t = head;
            head = head->next;
            t->next = nullptr;
            delete t; count--;
            return ret;
        }
        void clear() {
            while (head != nullptr) {
                node* t = head;
                head = head->next;
                t->next = nullptr;
                delete t;
            }
            count = 0;
        }
        ~Queue() {
            clear();
        }
        Queue& operator=(const Queue& q) {
            if (this != &q) {
                copy(q);
            }
            return *this;
        }
};


#endif