Finite-Automata/build.cpp at master · bmana21/Finite-Automata · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <utility>
#include <vector>
#include "NFA.h"


using namespace std;

pair<NFA *, int> build_NFA(string &expression, int start_index, bool do_star) {
    NFA *nfa = new NFA(true);
    bool operation = false;
    for (int k = start_index; k < (int) (expression.size()); k++) {
        if (expression[k] == '*') {
            nfa->star_NFA();
            continue;
        }
        if (expression[k] == '|') {
            auto ans = build_NFA(expression, k + 1, false);
            NFA *new_nfa = ans.first;
            k = ans.second;
            nfa->union_NFA(new_nfa);
            k = ans.second;
            if (k == (int) (expression.size()))
                continue;
        }
        if (expression[k] != '(' && expression[k] != ')') {
            operation = true;
            NFA *new_nfa = new NFA(false);
            auto *new_state = new state();
            new_state->index = 1;
            new_state->make_final();
            new_nfa->add_final_state(new_state);
            new_nfa->add_state(new_state);
            new_nfa->get_start_state()->add_transition(expression[k], new_state);
            new_state->add_incoming(expression[k], new_nfa->get_start_state());
            if (((k + 1) < (int) (expression.size())) && expression[k + 1] == '*') {
                new_nfa->star_NFA();
                k++;
            }
            nfa->concatenate_NFA(new_nfa);
            continue;
        }
        if (expression[k] == '(') {
            auto ans = build_NFA(expression, k + 1, true);
            NFA *new_nfa = ans.first;
            k = ans.second;
            if (!operation) {
                nfa->deep_delete();
                delete nfa;
                nfa = new_nfa;
                operation = true;
            } else {
                nfa->concatenate_NFA(new_nfa);
            }
            continue;
        }
        if (expression[k] == ')') {
            if (do_star)
                if (expression[k + 1] == '*') {
                    nfa->star_NFA();
                    k++;
                }
            return {nfa, k};
        }
    }
    return {nfa, (int) (expression.size())};
}

void solve_p1() {
    string expression;
    cin >> expression;
    auto answer_nfa = build_NFA(expression, 0, true).first;
    answer_nfa->print_NFA();
    answer_nfa->deep_delete();
    delete answer_nfa;
}

int main() {

    solve_p1();

    return 0;
}