LeetCode 题解工作台
解析布尔表达式
布尔表达式 是计算结果不是 true 就是 false 的表达式。有效的表达式需遵循以下约定： 't' ，运算结果为 true 'f' ，运算结果为 false '!(subExpr)' ，运算过程为对内部表达式 subExpr 进行 逻辑非 （NOT）运算 '&(subExpr 1 , subEx…
3
题型
6
代码语言
3
相关题
当前训练重点
困难 · 栈·状态
答案摘要
对于这种表达式解析问题，我们可以使用栈来辅助解决。 从左到右遍历表达式 `expression`，对于遍历到的每个字符 ：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
布尔表达式 是计算结果不是 true 就是 false 的表达式。有效的表达式需遵循以下约定：
't'，运算结果为true'f'，运算结果为false'!(subExpr)'，运算过程为对内部表达式subExpr进行 逻辑非（NOT）运算'&(subExpr1, subExpr2, ..., subExprn)'，运算过程为对 2 个或以上内部表达式subExpr1, subExpr2, ..., subExprn进行 逻辑与（AND）运算'|(subExpr1, subExpr2, ..., subExprn)'，运算过程为对 2 个或以上内部表达式subExpr1, subExpr2, ..., subExprn进行 逻辑或（OR）运算
给你一个以字符串形式表述的 布尔表达式 expression，返回该式的运算结果。
题目测试用例所给出的表达式均为有效的布尔表达式，遵循上述约定。
示例 1：
输入：expression = "&(|(f))" 输出：false 解释： 首先，计算 |(f) --> f ，表达式变为 "&(f)" 。 接着，计算 &(f) --> f ，表达式变为 "f" 。 最后，返回 false 。
示例 2：
输入：expression = "|(f,f,f,t)" 输出：true 解释：计算 (false OR false OR false OR true) ，结果为 true 。
示例 3：
输入：expression = "!(&(f,t))" 输出：true 解释： 首先，计算 &(f,t) --> (false AND true) --> false --> f ，表达式变为 "!(f)" 。 接着，计算 !(f) --> NOT false --> true ，返回 true 。
提示：
1 <= expression.length <= 2 * 104expression[i]为'('、')'、'&'、'|'、'!'、't'、'f'和','之一
解题思路
方法一：栈
对于这种表达式解析问题，我们可以使用栈来辅助解决。
从左到右遍历表达式 expression，对于遍历到的每个字符 ：
- 如果 是
"tf!&|"中的一个，我们直接将其入栈； - 如果 是右括号
')'，我们将栈中元素依次出栈，直到遇到操作符'!'或'&'或'|'。过程中我们用变量 和 记录出栈字符中't'和'f'的个数。最后根据出栈字符的个数和操作符计算得到新的字符't'或'f'，并将其入栈。
遍历完表达式 expression 后，栈中只剩下一个字符，如果是 't'，返回 true，否则返回 false。
时间复杂度 ，空间复杂度 。其中 是表达式 expression 的长度。
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
stk = []
for c in expression:
if c in 'tf!&|':
stk.append(c)
elif c == ')':
t = f = 0
while stk[-1] in 'tf':
t += stk[-1] == 't'
f += stk[-1] == 'f'
stk.pop()
match stk.pop():
case '!':
c = 't' if f else 'f'
case '&':
c = 'f' if f else 't'
case '|':
c = 't' if t else 'f'
stk.append(c)
return stk[0] == 't'
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Candidate effectively demonstrates understanding of stack-based state management.
- question_mark
Candidate uses recursion in a clear and effective way to handle nested operations.
- question_mark
Candidate implements helper functions that make the solution modular and readable.
常见陷阱
外企场景- error
Failing to correctly manage nested operations in the expression, leading to incorrect results.
- error
Not properly handling edge cases with multiple nested parentheses or complex operator combinations.
- error
Overcomplicating the solution by missing the stack's role in managing the expression's state.
进阶变体
外企场景- arrow_right_alt
Change the expression format to include additional boolean operations or nested expressions.
- arrow_right_alt
Implement this problem with different recursion depths or constraints, such as limiting parentheses.
- arrow_right_alt
Extend the problem to support more complex boolean operations like XOR or conditional (if-else).