leetcode/daily125.cpp at main · iFangg/leetcode · 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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// Solution 1
class Solution {
public:
    bool parseBoolExpr(string expr) {
        if (expr.size() == 1) {
            if (expr[0] == 't')
                return true;

            return false;
        }

        if (expr[0] == '&') {
            index += 2;
            return eval_expr(expr, true);
        }

        if (expr[0] == '|') {
            index += 2;
            return eval_expr(expr, false);
        }

        if (expr[0] == '!') {
            index += 2;
            return !eval_expr(expr, false);
        }

        return false;
    }

private:
        /*
        keep track of current expression
        recursive solution

        any & ! or | will be immediately followed by a bracket
            brackets will only appear for these compound expressions
            inside brackets may be another operation or subexpressions
            subtring to be passed in can be cut 2 indexes ahead instead of 1

            while closing brace has not been found, determine next

        else gather subexpressions and evaluate
        */

    bool eval_expr(std::string expr, bool is_and) {
        auto subexprs = std::vector<bool>{};

        while (index < expr.size() and expr[index] != ')') {
            // std::cout << expr[index] << std::endl;
            // find sub expressions
            if (expr[index] == '&') {
                // figure out all subexpr's with a while loop?
                index += 2;
                subexprs.push_back(eval_expr(expr, true));
            } else if (expr[index] == '|') {
                index += 2;
                subexprs.push_back(eval_expr(expr, false));
            } else if (expr[index] == '!') {
                index += 2;
                subexprs.push_back(!eval_expr(expr, false));
            } else {
                if (expr[index] == 't')
                    subexprs.push_back(true);
                else if (expr[index] == 'f')
                    subexprs.push_back(false);
            }

            index++;
        }

        bool res = subexprs[0];

        for (auto i = 1; i < subexprs.size(); ++i) {
            if (is_and)
                res &= subexprs[i];
            else
                res |= subexprs[i];
        }

        return res;
    }

    int index = 0;
};


// Solution 2
class Solution {
public:
    bool andd(string exp){
        int n = exp.length(), j=0;
        string subexp;
        int active = 0;
        while(j<n){
            if(active == 0 && exp[j]==','){
                if(!parseBoolExpr(subexp)) return false;
                subexp = "";
                j++;
                continue;
            }
            if(exp[j]=='(') active++;
            if(exp[j]==')') active--;
            subexp += exp[j++];
        }
        if(!parseBoolExpr(subexp)) return false;
        return true;
    }

    bool orr(string exp){
        int n = exp.length(), j=0;
        string subexp;
        int active = 0;
        while(j<n){
            if(active==0 && exp[j]==','){
                if(parseBoolExpr(subexp)) return true;
                subexp = "";
                j++;
                continue;
            }
            if(exp[j]=='(') active++;
            if(exp[j]==')') active--;
            subexp += exp[j++];
        }
        if(parseBoolExpr(subexp)) return true;
        return false;
    }

    bool parseBoolExpr(string exp) {
        int n = exp.length();
        if(n==1) return (exp[0]=='t');
        if(exp[0] == '!') return !parseBoolExpr(exp.substr(2, n-3));
        if(exp[0] == '&') return andd(exp.substr(2, n-3));
        if(exp[0] == '|') return orr(exp.substr(2, n-3));
        return false;
    }
};