LeetCode: 1106. 解析布尔表达式¶

1、题目描述¶

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

输入：expression = "!(f)"



输入：expression = "|(f,t)"



输入：expression = "&(t,f)"



输入：expression = "|(&(t,f,t),!(t))"



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

2、解题思路¶

• 使用栈，分别保存下面的元素

• 保存操作符：|&!
• 保存当前为True还是False
• 保存当前操作符下有几个操作数
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
stack_sign = []
stack_operand = []
stack_index = []

def process():
sign = stack_sign.pop()
last_index = stack_index.pop()
if sign == "!":
stack_operand[-1] = not stack_operand[-1]
elif sign == "|":
stack_operand[-last_index:] = [any(stack_operand[-last_index:])]
elif sign == "&":
stack_operand[-last_index:] = [all(stack_operand[-last_index:])]

for index, c in enumerate(expression):
if c in ["&", "|", "!"]:
stack_sign.append(c)
if stack_index:
stack_index[-1] += 1
elif c == "(":
stack_index.append(0)
elif c == "t":
stack_operand.append(True)
stack_index[-1] += 1
elif c == "f":
stack_operand.append(False)
stack_index[-1] += 1
elif c == ")":
process()

return stack_operand[-1]


class Solution:
def parseBoolExpr(self, expression: str) -> bool:
stack_sign = []
stack_operand = []
stack_index = []

def process():
sign = stack_sign.pop()
last_index = stack_index.pop()
if sign == "!":
stack_operand[-1] = not stack_operand[-1]
elif sign == "|":
stack_operand[-last_index:] = [any(stack_operand[-last_index:])]
elif sign == "&":
stack_operand[-last_index:] = [all(stack_operand[-last_index:])]
if stack_index:
stack_index[-1] += 1

index = 0
length = len(expression)
while index < length:
# 短路操作
if stack_sign and stack_index and stack_operand:
flag = False
if stack_sign[-1] == "&" and stack_index[-1] and not stack_operand[-1]:
flag = True
if stack_sign[-1] == "|" and stack_index[-1] and stack_operand[-1]:
flag = True

if flag:
left = 1
temp_pos = index
while left > 0:
if expression[temp_pos] == "(":
left += 1
elif expression[temp_pos] == ")":
left -= 1
temp_pos += 1
index = temp_pos
process()
if index >= length:
break
c = expression[index]
if c in ["&", "|", "!"]:
stack_sign.append(c)
stack_index.append(0)

elif c == "t":
stack_operand.append(True)
stack_index[-1] += 1
elif c == "f":
stack_operand.append(False)
stack_index[-1] += 1
elif c == ")":
process()
index += 1
return stack_operand[-1]