LC 1106. 解析布尔表达式

题目描述

这是 LeetCode 上的 1106. 解析布尔表达式 ，难度为困难。

给你一个以字符串形式表述的 布尔表达式 （boolean） expression，返回该式的运算结果。

有效的表达式需遵循以下约定：

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

示例 1：

输入：expression = "!(f)"

输出：true

示例 2：

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

输出：true

示例 3：

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

输出：false

示例 4：

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

输出：false

提示：

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

---

双栈

为了方便，我们令 expression 为 s。

我们可以将 t 和 f 看做操作数，而 |、& 和 ! 看做操作符，创建两个栈 nums 和 ops 分别对其进行存储。

剩余的 () 和 , 则只是优先级和分隔符，无须额外关注。

从前往后处理 s，根据当前处理的字符为何值进行分情况讨论：

• ,：分隔符，直接跳过；
• t 或 f：操作数，添加到 nums 栈中；
• |、& 或 !：操作符，添加到 ops 栈中；
• (：子表达式的左端点，为了在我们从「双栈」中取出数值和符号计算时，可以知道某个子表达式计算完成，需要记录一下。往 nums 追加一个占位符号 - 来代指；
• )：子表达式的右端点，代表一个子表达式的结束。可从「双栈」中取出符号和数组进行计算（在 ops 中仅取栈顶元素，代表当前子表达式的操作符；而在 nums 中则取到代表左端点的占位元素 - 为止），并将结果重新放入 nums 中。

最后考虑如何计算最简表达式，考虑实现一个 char calc(char a, char b, char op) 函数，代表对操作数 a 和 b 执行 op 操作并进行结果返回。

实际上，在 calc 函数我们只区分 | 操作和其他操作即可。也就是说 & 和 ! 均当做 & 来做，! 操作在计算完整个表达式后再翻转。

Java 代码：

class Solution {
    public boolean parseBoolExpr(String s) {
        Deque<Character> nums = new ArrayDeque<>(), ops = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == ',') continue;
            if (c == 't' || c == 'f') nums.addLast(c);
            if (c == '|' || c == '&' || c == '!') ops.addLast(c);
            if (c == '(') nums.addLast('-');
            if (c == ')') {
                char op = ops.pollLast(), cur = ' ';
                while (!nums.isEmpty() && nums.peekLast() != '-') {
                    char top = nums.pollLast();
                    cur = cur == ' ' ? top : calc(top, cur, op);
                }
                if (op == '!') cur = cur == 't' ? 'f' : 't';
                nums.pollLast(); nums.addLast(cur);
            }
        }
        return nums.peekLast() == 't';
    }
    char calc(char a, char b, char op) {
        boolean x = a == 't', y = b == 't';
        boolean ans = op == '|' ? x | y : x & y;
        return ans ? 't' : 'f';
    }
}

C++ 代码：

class Solution {
public:
    bool parseBoolExpr(string s) {
        deque<char> nums, ops;
        for (char c : s) {
            if (c == ',') continue;
            if (c == 't' || c == 'f') nums.push_back(c);
            if (c == '|' || c == '&' || c == '!') ops.push_back(c);
            if (c == '(') nums.push_back('-');
            if (c == ')') {
                char op = ops.back(); ops.pop_back();
                char cur = ' ';
                while (!nums.empty() && nums.back() != '-') {
                    char top = nums.back(); nums.pop_back();
                    cur = cur == ' ' ? top : calc(top, cur, op);
                }
                if (op == '!') cur = cur == 't' ? 'f' : 't';
                nums.pop_back(); nums.push_back(cur);
            }
        }
        return nums.back() == 't';
    }
    char calc(char a, char b, char op) {
        bool x = a == 't', y = b == 't';
        bool ans = op == '|' ? x | y : x & y;
        return ans ? 't' : 'f';
    }
};

Python 代码：

class Solution:
    def parseBoolExpr(self, s: str) -> bool:
        def calc(a, b, op):
            x, y = a == 't', b == 't'
            ans = x | y if op == '|' else x & y
            return 't' if ans else 'f'
        nums, ops = [], []
        for c in s:
            if c == ',':
                continue
            if c == 't' or c == 'f':
                nums.append(c)
            if c == '|' or c == '&' or c == '!':
                ops.append(c)
            if c == '(':
                nums.append('-')
            if c == ')':
                op, cur = ops.pop(), ' '
                while nums and nums[-1] != '-':
                    top = nums.pop()
                    cur = top if cur == ' ' else calc(cur, top, op)
                if op == '!':
                    cur = 't' if cur == 'f' else 'f'
                nums.pop()
                nums.append(cur)
        return nums[-1] == 't'

TypeScript 代码：

function parseBoolExpr(s: string): boolean {
    function calc(a: string, b: string, op: string): string {
        const x = a == 't', y = b == 't'
        const ans = op == '|' ? x || y : x && y
        return ans ? 't' : 'f'
    }
    const nums = new Array<string>(s.length).fill(''), ops = new Array<string>(s.length).fill('')
    let idx1 = 0, idx2 = 0
    for (const c of s) {
        if (c == ',') continue
        if (c == 't' || c == 'f') nums[idx1++] = c
        if (c == '|' || c == '&' || c == '!') ops[idx2++] = c
        if (c == '(') nums[idx1++] = '-'
        if (c == ')') {
            let op = ops[--idx2], cur = ' '
            while (idx1 > 0 && nums[idx1 - 1] != '-') {
                const top = nums[--idx1]
                cur = cur == ' ' ? top : calc(top, cur, op)
            }
            if (op == '!') cur = cur == 't' ? 'f' : 't'
            idx1--; nums[idx1++] = cur
        }
    }
    return nums[idx1 - 1] == 't'
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1106 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。