力扣每日一题 1106. 解析布尔表达式

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

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

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

栈模拟过程

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:

        stack = []
        left = -1

        for index, ex in enumerate(expression):
            if ex == ",":
                continue
            if ex == ")":
                print(stack)
                dic_count = {"f":0,"t":0}
                while stack[-1] != "(":
                    if stack[-1] == "(":
                        break
                    dic_count[stack[-1]] += 1
                    stack.pop()
                stack.pop()  # 删除左括号
                if stack[-1] == "!":
                    if dic_count["f"]:
                        stack.pop()
                        stack.append("t")
                    if dic_count["t"]:
                        stack.pop()
                        stack.append("f")
                
                if stack[-1] == "|":
                    if dic_count["t"]:
                        stack.pop()
                        stack.append("t")
                    else:
                        stack.pop()
                        stack.append("f")
                if stack[-1] == "&":
                    if dic_count["f"]:
                        stack.pop()
                        stack.append("f")
                    else:
                        stack.pop()
                        stack.append("t")
            if ex != ")":
                stack.append(ex)
        if stack[0] == "f":
            return False
        else:
            return True
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

1. 左括号与右括号匹配，遍历所有字符，逗号跳过，其他元素入栈，当遍历到右括号的时候出栈，直到碰到左括号的时候，出栈完毕
2. 出栈的元素更具逻辑符号判断是false还是true
3. 当是！的时候，反正，如果是|则看是否有True ,如果有&则看是否有False
4. 最后把左括号出栈，把计算出的值，入栈
5. 最后占中剩一个元素，取出则为答案