解析布尔表达式

标签: 栈 递归 字符串

难度: Hard

布尔表达式 是计算结果不是 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' 和 ',' 之一

Submission

运行时间: 42 ms

内存: 16.7 MB

from sortedcontainers import SortedList
from typing import List
from collections import defaultdict, deque
from itertools import accumulate
from functools import cache
import sys
import math
inf=float("inf")

class Solution:
    def log(self, *s):
        pass
    
    def parseBoolExpr(self,expr:str):
        expr=expr.replace(',','')
        # print(expr)
        def dfs(op,args:str):
            self.log(f'{op}:{args}')
            l,r=0,len(args)-1
            while l<=r:
                if args[l]=='f':
                    tmp_result=False
                elif args[l]=='t':
                    tmp_result=True
                else:
                    if op == '!':
                        right_index=r-l
                    else:
                        right_index=args[l:].index(')')
                    tmp_result = dfs(args[l],args[l+2:l+right_index])
                    l+=right_index
                if op == '&' and tmp_result==False:
                    return False
                elif op == '|' and tmp_result == True:
                    return True
                elif op=='!':
                    return not tmp_result
                l+=1   
            return True if op=='&' else False 
        return dfs(expr)
    def parseBoolExpr(self,expr:str):
        expr=expr.replace(',','')
        stacks=[]
        stack_values=[[]]
        for i,v in enumerate(expr):
            if v == '(':
                stack_values.append([])
                stacks.append(expr[i-1])
            elif v==')':
                op=stacks.pop()
                vs=stack_values.pop()
                if op=='&':
                    flag=all(vs)
                elif op=='|':
                    flag=any(vs)
                elif op=='!':
                    flag=not vs[0]
                # self.log(op,stack_values[:],vs,flag)
                stack_values[-1].append(flag)
               
            elif v=='f':
                stack_values[-1].append(False)
            elif v=='t':
                stack_values[-1].append(True)
            
        return stack_values[0][0]
    
    def run(self, *args):
        return self.parseBoolExpr(*args)


class SolutionDebug(Solution):
    logs = ""

    def log(self, *s):
        self.logs += " ".join([str(v) for v in s])+"
"

    def run(self, *args, **kw) -> int:
        self.logs = ""
        try:
            return super().run(*args, **kw)
        except Exception as e:
            import traceback
            traceback.print_exc()
            return None


if __name__ == '__main__':
    s = SolutionDebug()
    null=None
    true=True
    false=False
    for case in [
        ["|(&(t,f,t),t)",True],
        ["!(&(!(&(f)),&(t),|(f,f,t)))",False],
        ["!(&(!(t),&(f),|(f)))",true],
        ["|(&(t,f,t),!(t))",false],
        ["&(|(f))",false],
        ["|(f,f,f,f,t)",true],
        ["!(&(f,t))",true]
    ]:
        s.logs = ""
        e = s.run(*case[:-1])
        if e != case[-1]:
            print(e, case)
            print(s.logs)
            break

Explain

该题解使用栈的方法解析并计算布尔表达式的值。首先，将表达式中的逗号删除以简化解析过程。接着，遍历处理表达式的每个字符。遇到左括号时，初始化一个新的栈用于存储当前子表达式的值，并记录当前运算符。遇到右括号时，根据之前记录的运算符从栈中取出所有子表达式的值，进行相应的逻辑运算（AND, OR, NOT），并将结果存入上一个栈。对于 'f' 和 't', 直接转换为布尔值 False 或 True 并存入当前栈。最终，栈顶元素即为整个表达式的计算结果。

时间复杂度: O(n)

空间复杂度: O(n)

from sortedcontainers import SortedList
from typing import List
from collections import defaultdict, deque
from itertools import accumulate
from functools import cache
import sys
import math
inf=float(\"inf\")

class Solution:
    def log(self, *s):
        pass  # 日志打印函数，用于调试
    
    def parseBoolExpr(self,expr:str):
        expr=expr.replace(',','')  # 删除所有逗号以简化解析
        stacks=[]  # 运算符栈
        stack_values=[[]]  # 存储布尔值的栈
        for i,v in enumerate(expr):
            if v == '(':
                stack_values.append([])  # 遇到左括号，为子表达式创建新的栈
                stacks.append(expr[i-1])  # 记录当前运算符
            elif v==')':
                op=stacks.pop()  # 取出运算符
                vs=stack_values.pop()  # 取出当前栈的所有布尔值
                if op=='&':
                    flag=all(vs)  # 执行AND运算
                elif op=='|':
                    flag=any(vs)  # 执行OR运算
                elif op=='!':
                    flag=not vs[0]  # 执行NOT运算
                stack_values[-1].append(flag)  # 将结果存入上一个栈
            elif v=='f':
                stack_values[-1].append(False)  # 处理'f'为False
            elif v=='t':
                stack_values[-1].append(True)  # 处理't'为True
        return stack_values[0][0]  # 返回栈顶元素，即整个表达式的计算结果

Explore

在布尔表达式中，逗号通常用来分隔同一层级内的多个子表达式或值。在解析这类表达式时，删除逗号之后，只要保证不改变各个子表达式之间的边界和层级关系，就不会影响表达式的结构或意义。具体到算法实现中，通过在遇到左括号时创建新栈，以及在遇到右括号时处理所有层级内的表达式，可以确保即使逗号被移除，子表达式的界限和处理顺序仍被正确维护。

遇到左括号标志着一个新的子表达式的开始，这时使用新栈来保存这个子表达式的值是为了隔离不同层级和上下文的数据，确保每个表达式可以独立计算。这种栈的使用方法非常适合处理嵌套表达式，因为它自然地符合表达式的嵌套和层级结构，每遇到一个新的子表达式就创建一个新栈，直到遇到对应的右括号才将这个栈的结果汇总到上一级栈中。这种方法的效率通常与表达式的深度（即嵌套层数）成正比，因为每个表达式的计算是独立的，虽然对于深层嵌套的表达式会增加栈的操作，但总体上是高效且适合这类问题的解法。

操作符'!', '与', '|'的逻辑处理在逻辑上是准确的，因为它们直接对应于布尔逻辑的基本运算。然而，在效率方面，如果一个表达式中包含大量的子表达式，尤其是对于'与'和'|'操作，需要对所有子表达式进行遍历和运算，这可能会导致效率问题。特别是，'与'操作如果在某个子表达式为假的情况下仍然继续计算其他子表达式，或者'|'操作在某个子表达式为真的情况下仍然继续，都会导致不必要的计算，从而影响性能。在实现时，可以通过短路逻辑来优化这些操作，即在'与'操作中一旦遇到假值即停止后续计算，在'|'操作中一旦遇到真值即停止后续计算，以提高效率。