解析布尔表达式 : 双栈求解表达式问题

骑猪看日落 2023-09-23 14:12 114阅读 0赞

### 题目描述 ###

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

Tag : 「栈」、「表达式计算」

给你一个以字符串形式表述的 布尔表达式 `（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<=200001 <= expression.length <= 200001<=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';
        }
    }
    复制代码

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'
    }
    复制代码

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'
    复制代码

*  时间复杂度：O(n)O(n)O(n)
 *  空间复杂度：O(n)O(n)O(n)

[1106.]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fparsing-a-boolean-expression%2Fsolution%2Fby-ac_oier-jr29%2F