题目
给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。
有效的表达式需遵循以下约定：
- “t”，运算结果为 True
- “f”，运算结果为 False
- “!(expr)”，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
- “&(expr1,expr2,…)”，运算过程为对 2 个或以上内部表达式 expr1, expr2, … 进行逻辑与的运算（AND）
- “|(expr1,expr2,…)”，运算过程为对 2 个或以上内部表达式 expr1, expr2, … 进行逻辑或的运算（OR）
示例
示例 1：
输入：expression = “!(f)”
输出：true
示例 2：
输入：expression = “|(f,t)”
输出：true
示例 3：
输入：expression = “&(t,f)”
输出：false
示例 4：
输入：expression = “|(&(t,f,t),!(t))”
输出：false
提示：
1 <= expression.length <= 20000
expression[i] 由 {‘(’, ‘)’, ‘&’, ‘|’, ‘!’, ‘t’, ‘f’, ‘,’} 中的字符组成。
expression 是以上述形式给出的有效表达式，表示一个布尔值。
思路
- 遇到带有括号的题第一时间应该就想到栈
- 这里使用栈signals记录所有运算符号，用栈number记录所有的操作数
- 遍历一遍给定的expression，可能会遇到以下情况
- 遇到’!‘或’&‘或’|'，这几个就是运算符号，我们直接依次压入栈signals中
- 遇到’t’或’f’，这俩是操作数，我们可以依次压入number中
- 遇到’('，左括号作为分割与前一个括号的分隔符，我们可以向栈number中压入空字符串来辨识
- 遇到’)'，遇到右括号证明我们要向前方直至上一个分隔符进行运算了，这时候对应signals的栈顶元素也就是我们所需要的运算符号，我们弹出signals的栈顶元素记作signal。然后依次弹出number中的元素（直到遇到空字符串停止）做signal运算，最后删除分隔符，将运算结果再压入栈中供后面使用即可
- 直到遍历完给定expression中的元素，number栈中必定只剩下最后一个结果元素，返回即可
题解
class Solution: def parseBoolExpr(self, expression: str) -> bool: # 定义运算符号和操作数栈 signals = [] number = [] # 遍历 for i in expression: # 遇到运算符 if i in '!|&': signals.append(i) # 遇到操作数 elif i == 't' or i == 'f': # 注意压入的是True和False number.append(True if i == 't' else False) # 遇到右括号 elif i == ')': # 弹出运算符 signal = signals.pop() # 下面分情况进行运算 tmp = number.pop() # ！直接取反即可，但是要先删除空字符串 if signal == '!': number.pop() number.append(not tmp) elif signal == '&': # 弹到分隔符为止，下同理 while number[-1] !='': tmp_ = number.pop() tmp = tmp and tmp_ number.pop() number.append(tmp) else: while number[-1] != '': tmp_ = number.pop() tmp = tmp or tmp_ number.pop() number.append(tmp) # 遇到左括号 elif i == '(': number.append('') # 返回number首元素即可 return number[0]
