目录

1106:解析布尔表达式(1880 分)

力扣第 143 场周赛第 4 题

题目

布尔表达式 是计算结果不是 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 * 104
  • expression[i]'('')''&''|''!''t''f'',' 之一

分析

栈模拟递归即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        sk = [[]]
        for c in expression:
            if c in '!&|':
                sk.append([c])
            elif c in 'tf':
                sk[-1].append(c=='t')
            elif c==')':
                A = sk.pop()
                x = A[1]^1 if A[0]=='!' else reduce(and_ if A[0]=='&' else or_,A[1:])
                sk[-1].append(x)
        return bool(sk[0][0])

19 ms