LeetCode 1106. 解析布尔表达式

约 6 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 腾讯 字节 华为
标签
字符串 栈 递归

题目描述

✅ 1106. 解析布尔表达式

image-20260928225745386

image-20260928225745387

题意分析

计算一个合法布尔表达式的值。t 表示真，f 表示假；! 对一个子表达式取反，& 对一个或多个子表达式求与，| 对一个或多个子表达式求或。运算符写在参数括号之前，多个参数以逗号分隔，并且可以任意嵌套。

输入保证语法合法，不需要另做语法纠错。求值必须遵守括号结构，不能把扫描过程中最先遇到的真假值当成最终答案；表达式也可能只有单独一个 t 或 f。

解法：栈归约表达式

核心思路

[!blue]

从左到右扫描，用栈保存尚未计算完的内容。字面量、运算符和左括号直接入栈，逗号只是参数分隔符，可以跳过。遇到右括号时，这一层参数已经读完，可以立即计算并把整个子表达式替换成一个真假值。

为什么右括号处能直接计算？它关闭的是最近尚未关闭的左括号。嵌在本层内部的表达式更早遇到了各自右括号，已经被压缩成 t 或 f，因此从栈顶弹到对应左括号之间只会得到本层已计算好的参数，不会夹着尚未完成的内层运算。

不需要保存全部参数内容，只需记录本层是否出现真、是否出现假。取反只有一个参数，出现假则结果为真；与运算只要有假就为假，所以结果是 !hasFalse；或运算只要有真就为真，所以结果是 hasTrue。取出参数后，再弹出左括号和它前面的运算符，压回一个结果字符。

这一替换保留了外层所需的全部信息，外层只关心子表达式的值，不关心它的内部写法。扫描结束后，整个表达式缩成一个栈内值；没有括号的单个字面量也会直接留在栈中。

即使本层的与或结果已经确定，仍要消费其余参数和括号来找到正确边界，不能直接结束整体扫描。显式栈同时避免了把输入嵌套深度直接转化成函数调用深度。

解题步骤

  1. 创建空字符栈，从左向右读字符。
  2. 逗号跳过；不是右括号的其他字符直接压栈。
  3. 遇到右括号时，弹出真假值直到左括号，记录本层的 hasTrue 和 hasFalse。
  4. 弹出左括号，再弹出运算符，根据取反、与、或的规则计算结果。
  5. 把结果压回为一个 t 或 f，供外层表达式继续使用。
  6. 扫描完后根据栈中唯一的真假值返回。

代码实现

class Solution {
    public boolean parseBoolExpr(String expression) {
        char[] stack = new char[expression.length()];
        int top = 0;

        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);

            // 逗号只分隔参数，不作为操作数入栈。
            if (ch == ',') {
                continue;
            }

            if (ch != ')') {
                stack[top++] = ch;
                continue;
            }

            boolean hasTrue = false;
            boolean hasFalse = false;

            // 内层已归约为真假值，收集当前括号内的全部操作数。
            while (stack[top - 1] != '(') {
                char value = stack[--top];

                if (value == 't') {
                    hasTrue = true;
                } else {
                    hasFalse = true;
                }
            }

            top--;
            // 弹出左括号后再取操作符，一层只压回一个真假结果。
            char operator = stack[--top];
            boolean result;

            if (operator == '!') {
                result = hasFalse;
            } else if (operator == '&') {
                result = !hasFalse;
            } else {
                result = hasTrue;
            }

            // 结果替换整个子表达式，留给外层运算使用。
            stack[top++] = result ? 't' : 'f';
        }

        return stack[0] == 't';
    }
}

func parseBoolExpr(expression string) bool {
    stack := make([]byte, 0, len(expression))
    for i := 0; i < len(expression); i++ {
        ch := expression[i]
        // 逗号只分隔参数，不作为操作数入栈。
        if ch == ',' {
            continue
        }
        if ch != ')' {
            stack = append(stack, ch)
            continue
        }

        hasTrue, hasFalse := false, false
        // 内层已归约为真假值，收集当前括号内的全部操作数。
        for stack[len(stack)-1] != '(' {
            value := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if value == 't' {
                hasTrue = true
            } else {
                hasFalse = true
            }
        }
        stack = stack[:len(stack)-1]
        // 弹出左括号后再取操作符，一层只压回一个真假结果。
        operator := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result := false
        if operator == '!' {
            result = hasFalse
        } else if operator == '&' {
            result = !hasFalse
        } else {
            result = hasTrue
        }
        // 结果替换整个子表达式，留给外层运算使用。
        if result {
            stack = append(stack, 't')
        } else {
            stack = append(stack, 'f')
        }
    }
    return stack[0] == 't'
}

复杂度分析

  • 时间复杂度：O(n)。每个输入字符读取一次，每个入栈项最多弹出一次；每次归约只增加一个结果，归约次数不超过括号对数量。
  • 空间复杂度：O(n)。尚未归约的运算符、括号和参数存放在显式栈中。

关键点总结

[!green]

  • 右括号给出一个完整子表达式的结束点，栈保证内层先于外层归约。
  • 已完成子表达式统一表示成一个真假字符，使每一层都使用同样的计算规则。
  • 与、或只需真假是否出现的信息，不需要重新保存或拼接表达式。
  • 数值已确定不等于语法已消费完，仍要正确处理嵌套边界。

易错点总结

[!yellow]

  • 把逗号当作操作数入栈：会污染本层真假统计，逗号只负责分隔。
  • 遇到真或假就立即返回：当前值可能还受外层取反或与、或运算影响。
  • 没弹出左括号就取运算符：运算符位于左括号之前，弹出次序不能混乱。
  • 为与运算使用 hasTrue：有真不代表全部为真，应检查是否不存在假。
  • 只计算不把结果压回栈：外层会失去这个参数，必须用一个真假值替换整个子表达式。

相似题目

题目 难度 关联与区别
736. Lisp 语法解析 困难 同样递归解析前缀形式与括号，本题运算值只有真假，不需要变量环境。
224. 基本计算器 困难 同样按嵌套结构求值，但本题运算符位于参数括号前，并可有多个逗号分隔参数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/87972596
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！