LeetCode 1106 解析布尔表达式[栈] HERODING的LeetCode之路

思路

读罢题目很容易联想到计算器的操作，思路都是一样的，只不过不是加减乘除，也不是简单的数字了，变成了更简单的bool运算和bool值，那么我们可以考虑用同样的方法，即双栈，一个栈存储运算符，一个栈存储bool值。

解题方法

根据思路，首先遍历整个表达式，遇到操作符就存在操作栈中，遇到布尔值就以0和1存在计算栈中，为了更好计算，对于输入的’(‘，标记为-1作为计算的分隔线，当遇到’)'时，开始计算，拿到操作栈顶的操作符，对计算栈中分割线-1以上的所有元素进行计算，计算完毕把分隔符pop出来，再把当前的计算结果放入。最后计算栈中只剩下一个元素，即最终的计算结果，返回即可。

复杂度

• 时间复杂度: $O(n)$，即遍历一遍表达式。

• 空间复杂度: $O(n)$，空间复杂度主要取决于栈空间，栈内字符个数不超过 $n$。

Code

class Solution {
public:
    bool parseBoolExpr(string expression) {
        // 算符栈
        stack<char> opertion;
        // 计算栈
        stack<int> s;
        for(int i = 0; i < expression.size(); i ++) {
            // 左括号标记为-1作为计算的分割线
            if(expression[i] == '(') {
                s.push(-1);
            } else if(expression[i] == 'f' || expression[i] == 't') {
                s.push(expression[i] == 'f' ? 0 : 1);
            } else if(expression[i] == '!' || expression[i] == '&' || expression[i] == '|') {
                opertion.push(expression[i]);
            } else if(expression[i] == ')') {
                if(!opertion.empty()) {
                    char op = opertion.top();
                    opertion.pop();
                    if(!s.empty()) {
                        int temp = s.top();
                        s.pop();
                        if(op == '!') {
                            temp = abs(temp - 1);
                        } else if(op == '&') {
                            while(!s.empty() && s.top() != -1) {
                                temp *= s.top();
                                s.pop();
                            } 
                        } else {
                            while(!s.empty() && s.top() != -1) {
                                temp |= s.top();
                                s.pop();
                            } 
                        }
                        s.pop();
                        s.push(temp);
                    }
                }
            }
        }
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