[LeetCode] 1106. 解析布尔表达式

思路

从题目中可以得出，一个表达式是通过 n(n>=1) 个表达式并列、嵌套而成。其实很像前缀表达式。

这样我们很容易想到通过递归的方式来做，递归的边界条件就是 "t" 或者 "f"。

在递归的过程中实际上是不断地缩小问题的规模，直到能够得出问题最终的答案。

在缩小问题规模的时候有两种情况：

1. 嵌套
2. 并列

• 对于嵌套的情况，只要去掉外面的操作符和括号，我们就可以得到一个新的规模更小的表达式。
• 对于并列的情况，我们需要对表达式进行分割，关键在于如何知道这些并列的表达式之间的界限

直接按照逗号进行分割是不行的，因为一个完整的表达式内部也可能有逗号。

对于这种情况，我们可以使用栈来得到表达式的边界：

而栈又可以模拟递归的过程，所以就可以直接使用栈来解决这个问题。

总结：对于前缀表达式这样的题，栈是比较优秀的解法。

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stk = []
        for c in expression:
            if c == ',':
                continue
            if c != ')':
                stk.append(c)
                continue
            t = f = 0
            while stk[-1] != '(':
                if stk.pop() == 't':
                    t += 1
                else:
                    f += 1
            stk.pop()
            op = stk.pop()
            if op == '!':
                stk.append('t' if f == 1 else 'f')
            elif op == '&':
                stk.append('t' if f == 0 else 'f')
            elif op == '|':
                stk.append('t' if t else 'f')
        return stk[-1] == 't'