跳到主要内容

1106.解析布尔表达式

· 阅读需 3 分钟

1、题干​

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

Problem: 1106. 解析布尔表达式

[TOC]

思路

使用正则不断提取最小表达式进行计算，再将该表达式替换为计算结果。其中最小表达式就是题干中给出的3种情况："!(expr)"，"&(expr1,expr2,...)"，"|(expr1,expr2,...)"

代码


function parseBoolExpr(exp: string): boolean {
    const T = "t", F = "f", reg = /.\([^()]+\)/g;
    while (reg.test(exp)) {
        exp = exp.replace(reg, (m) => {
            if (m[0] === "&") return m.includes(F) ? F : T;
            if (m[0] === "|") return m.includes(T) ? T : F;
            return m.includes(T) ? F : T;
        });
    }
    return exp.includes(T);
}

结果

image.png