题目：

给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。

有效的表达式需遵循以下约定：

"t"，运算结果为 True
"f"，运算结果为 False
"!(expr)"，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
"&(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 与的运算（AND）
"|(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 或的运算（OR）

示例 1：

1
2
输入：expression = "!(f)"
输出：true

示例 2：

1
2
输入：expression = "|(f,t)"
输出：true

示例 3：

1
2
输入：expression = "&(t,f)"
输出：false

示例 4：

1
2
输入：expression = "|(&(t,f,t),!(t))"
输出：false

提示：

1 <= expression.length <= 20000
expression[i] 由 {'(', ')', '&', '|', '!', 't', 'f', ','} 中的字符组成。
expression 是以上述形式给出的有效表达式，表示一个布尔值。

解题思路：

就是常规的模拟，看到解析式我们第一个要想到的就是栈

  1. 字符为,跳过
  2. 字符为) 解析布尔表达式
    1. 不断弹出栈顶，直到栈顶为(
    2. 解析表达式
  3. 字符为其他 推入栈中

代码：

Python

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
class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stack = []
        t = f = 0

        for s in expression:
            if s == ',':
                continue
            elif s == ')':
                while stack[-1] != '(':
                    if stack.pop() == 't':
                        t += 1
                    else:
                        f += 1
                stack.pop()
                sign = stack.pop()
                if sign == '!':
                    stack.append('t' if f == 1 else 'f')
                elif sign == '|':
                    stack.append('t' if t >= 1 else 'f')
                else:
                    stack.append('t' if f == 0 else 'f')
                t = f = 0
            else:
                stack.append(s)
        return stack[-1] == 't'

C++

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
class Solution {
public:
    bool parseBoolExpr(string expression) {
        stack<char> stk;
        
        for (auto c: expression) {
            if (c == ',') continue;
            else if (c != ')') stk.push(c);
            else
            {
                int t = 0, f = 0;
                while (stk.top() != '(')
                {
                    if (stk.top() == 't') ++t;
                    else ++f;
                    stk.pop();
                }
                stk.pop();
                char sign = stk.top();
                stk.pop();
                if (sign == '!')
                {
                    stk.push(f == 1 ? 't': 'f');
                }
                else if (sign == '|')
                {
                    stk.push(t >= 1 ? 't': 'f');
                }
                else
                {
                    stk.push(f >= 1 ? 'f': 't');
                }
            }
        }
        return stk.top() == 't';
    }
};