LeetCode 1106. 解析布尔表达式

2025-06-08 HGNULB 约 10 分钟

文章信息 8 个分类 3 个标签

分类

题目描述

✅ 1106. 解析布尔表达式

题意分析

给一个字符串形式的布尔表达式，求它的真假值。表达式只有四种形态：字面量 t 和 f；取反 !(expr)，括号里恰好一个子表达式；合取 &(expr,expr,...) 和析取 |(expr,expr,...)，括号里有一个或多个子表达式，用逗号分隔。

定义本身就是递归的——子表达式又可以是这四种形态中的任意一种，且嵌套深度没有限制。这条性质决定了解法形态：要么显式用栈模拟嵌套，要么直接用函数调用栈做递归下降。

语法保证合法，这是一条很关键的放松：不需要做任何错误处理，括号一定配对，! 后面一定恰好一个参数，逗号一定出现在两个子表达式之间。因此可以放心地按位置「跳过」固定字符，不必反复校验。

边界包括：整个表达式可能就是单个 t 或 f；嵌套可以很深，需要注意递归深度；& 与 | 的参数个数可变，不能假设只有两个。

解法：递归下降解析

核心思路

先想显式栈的做法：从左往右扫，遇到 ) 就把栈里回退到最近的 (，取出这一段的所有布尔值和对应的操作符，算出结果再压回栈。这条路能走通，也是很多题解的写法，但它要在一个栈里混放操作符、括号和布尔值，出栈时还要判断类型，状态相当零碎。

换个角度：既然文法是递归定义的，那就让解析函数的结构直接照抄文法。这就是递归下降——为「一个表达式」写一个函数，它读完一个完整的表达式并返回其值，遇到子表达式就递归调用自己。函数调用栈替我们承担了原本要手工维护的那个栈。

让这套写法成立的核心是一个共享的读取位置 index，配上一条严格的调用约定，也就是本解法的不变量：每次调用 parse 时，index 必须正指向一个完整表达式的第一个字符；parse 返回时，index 必须正指向该表达式最后一个字符的下一个位置。

只要每个分支都维护这条约定，嵌套就自动正确了。字面量分支读一个字符后 index 加一，显然满足；! 分支先跳过 ! 和 ( 共两个字符，递归解析唯一的子表达式，此时 index 停在 ) 上，再加一跳过它，满足；&/| 分支同样先跳过两个字符，然后循环解析子表达式——每解析完一个，index 要么停在 , 上（跳过它继续下一个），要么停在 ) 上（跳过它并结束），满足。

还有一个容易被忽略的点：即使中途结果已经确定（& 遇到一个 false，或 | 遇到一个 true），也必须把剩余的子表达式解析完。因为这里的「解析」同时承担着推进 index 的职责，短路跳过会让 index 停在错误的位置，导致外层读到的字符全部错位。这也是为什么聚合用的是「先解析再合并」的顺序。

解题步骤

用一个跨调用共享的 index 表示当前读取位置。Java 里做成成员变量并在入口重置，Go 里用闭包捕获局部变量；把它做成参数传值是不行的，因为子调用推进的位置必须被父调用看见。

解析函数先看当前字符。若是 t 或 f，index 前进一位并返回对应布尔值，这是递归的出口。

否则当前字符一定是操作符。记下它，然后 index += 2 一次性跳过「操作符 + 左括号」两个字符。之所以能盲跳，是因为题目保证语法合法，操作符后面必然紧跟左括号。

若操作符是 !，递归解析唯一的子表达式，返回后 index 恰好停在配对的 ) 上，index++ 跳过它，返回取反的结果。这里不需要循环，因为 ! 的参数个数固定为一。

若是 & 或 |，先把结果初始化成该运算的单位元：& 初始化为 true、| 初始化为 false。这样第一次合并就不会引入偏差，也免去了「是否是第一个参数」的特判。

循环解析子表达式并把值合并进结果；每解析完一个就看当前字符：是 ) 就跳过它并结束本层，是 , 就跳过它继续下一个。判断放在解析之后而不是之前，正是靠了「parse 返回时 index 停在表达式末字符的下一位」这条约定。

顶层调用返回的就是整个表达式的值。

以 expression = "|(&(t,f,t),!(t))" 走一遍，下标依次是 0 |、1 (、2 &、3 (、4 t、5 ,、6 f、7 ,、8 t、9 )、10 ,、11 !、12 (、13 t、14 )、15 )。

顶层进入 parse，index = 0 读到 |，记下操作符后 index 跳到 2，result 初始化为 false，进入循环。

第一次递归解析从 index = 2 开始：读到 &，index 跳到 4，子结果初始化为 true。读 t 得 true，index = 5，子结果仍为 true；当前字符是 ,，index 前进到 6。读 f 得 false，index = 7，子结果变为 false；字符是 ,，index 前进到 8。读 t 得 true，index = 9，子结果 false && true 仍是 false——注意这里虽然结果已经注定是 false，但这个 t 依然被完整解析了，index 才得以正确推进；当前字符是 )，index 前进到 10 并结束本层，返回 false。

回到顶层：result 为 false || false = false；当前字符 index = 10 是 ,，index 前进到 11，继续循环。

第二次递归解析从 index = 11 开始：读到 !，index 跳到 13。递归解析得到 t 为 true，index = 14 停在 ) 上，index++ 变成 15，返回 !true = false。

回到顶层：result 为 false || false = false；当前 index = 15 是 )，index 前进到 16 并结束循环，返回 false。整串解析完毕，答案 false 与手算一致：&(t,f,t) 为假，!(t) 为假，两者相或仍为假。

代码实现

class Solution {
    private int index;

    public boolean parseBoolExpr(String expression) {
        index = 0;
        return parse(expression);
    }

    private boolean parse(String expression) {
        char ch = expression.charAt(index);
        if (ch == 't') {
            index++;
            return true;
        }
        if (ch == 'f') {
            index++;
            return false;
        }

        char operator = ch;
        index += 2;

        if (operator == '!') {
            boolean value = parse(expression);
            index++;
            return !value;
        }

        boolean result = operator == '&';
        while (true) {
            boolean value = parse(expression);
            if (operator == '&') {
                result = result && value;
            } else {
                result = result || value;
            }

            if (expression.charAt(index) == ')') {
                index++;
                break;
            }
            index++;
        }

        return result;
    }
}

func parseBoolExpr(expression string) bool {
    index := 0
    var parse func() bool

    parse = func() bool {
        ch := expression[index]
        if ch == 't' {
            index++
            return true
        }
        if ch == 'f' {
            index++
            return false
        }

        operator := ch
        index += 2

        if operator == '!' {
            value := parse()
            index++
            return !value
        }

        result := operator == '&'
        for {
            value := parse()
            if operator == '&' {
                result = result && value
            } else {
                result = result || value
            }

            if expression[index] == ')' {
                index++
                break
            }
            index++
        }

        return result
    }

    return parse()
}

复杂度分析

时间复杂度：$O(n)$，n 是表达式长度。index 只增不减，每个字符要么被某次调用直接消费，要么被一次跳过操作跨过，总推进量正好是 n。

空间复杂度：$O(n)$，递归深度等于括号的最大嵌套层数，最坏情况（形如 !(!(!(…t…)))）与表达式长度同阶；显式栈写法的空间瓶颈也是同一个量。

关键点总结

文法是递归定义的，解析器就该按文法的形状写：一个产生式对应一个分支，子表达式对应一次递归调用，函数调用栈替代手工维护的状态栈。

递归下降的正确性完全依赖一条调用约定——进入时 index 指向表达式首字符、返回时指向末字符的下一位。写之前把它说清楚，每个分支照着核对一遍，几乎不会写错。

共享的读取位置必须是可变且跨调用可见的（成员变量或闭包捕获），传值参数会让子调用的推进对父调用不可见，是这类题最典型的结构性错误。

当「解析」同时承担「推进位置」的职责时，绝不能因为结果已定而短路跳过剩余部分；想做短路优化，也必须先完整解析再丢弃结果。

可变参数个数的聚合运算，把结果初始化成单位元（& 用 true、| 用 false）能消掉「首个参数」的特判，这个技巧在求交集、求并集、求最大公约数时同样适用。

面试视角：面试官会关心你能否把「栈解法」和「递归解法」说成同一件事——递归下降就是把显式栈交给运行时管理。被追问深度嵌套导致栈溢出时，答案是改写成显式栈的迭代版本；被追问如何扩展到支持优先级和二元中缀运算符时，答案是把单函数拆成按优先级分层的多个 parse 函数。

易错点总结

错误写法：把 index 作为普通值参数传给递归函数 → 用例 "|(&(t,f,t),!(t))"，子调用推进的位置回不到父调用，外层读到的仍是旧位置的字符，解析立刻错乱甚至死循环。

错误写法：& 遇到 false 就直接 return 短路 → 用例 "|(&(t,f,t),!(t))"，&(t,f,t) 在读到 f 后提前返回，index 停在 7 而不是 10，外层把 ,t) 当成新的子表达式，最终结果错误。

错误写法：! 分支解析完子表达式后忘记 index++ 跳过右括号 → 用例 "!(f)"，index 停在 ) 上，顶层若还有后续内容会把 ) 当成表达式首字符，越界或读到非法字符。

错误写法：把 index += 2 写成 index += 1，只跳过操作符不跳左括号 → 用例 "&(t,t)"，递归时读到的首字符是 (，既不是字面量也不是已知操作符，逻辑直接走错分支。

错误写法：& 的结果初始化为 false → 用例 "&(t,t)"，false && true 恒为 false，返回 false，正确答案是 true。

错误写法：| 的结果初始化为 true → 用例 "|(f,f)"，返回 true，正确答案是 false。

错误写法：循环里先判断当前字符是不是 ) 再解析 → 用例 "&(t,f)"，进入循环时 index 指向 t 而不是分隔符，判断位置错位，第一个子表达式就被跳过。

错误写法：用 expression.charAt(index) == ',' 作为继续条件、其余情况一律结束 → 用例 "!(t)" 嵌套在 & 里时，遇到非逗号非右括号的字符会静默退出，index 不再推进，外层陷入死循环。

错误写法：Java 里把 index 写成 parse 的局部变量而非成员变量 → 用例 "&(t,f)"，每次递归都从 0 开始读，永远解析同一个字符，栈溢出。

错误写法：Java 里忘记在 parseBoolExpr 入口重置 index = 0 → 判题会复用同一个 Solution 实例连续调用多个用例，第二个用例的 index 从上一次的末尾开始，直接越界。

错误写法：把 t/f 的判断放在操作符判断之后 → 用例 "t"，t 被当成操作符执行 index += 2 后越界读取，抛异常。

相似题目

题目	难度	考察点
394. 字符串解码	中等	同样的嵌套括号结构，但要携带重复次数并拼接字符串
224. 基本计算器	困难	中缀表达式带正负号与括号，需处理一元负号与符号栈
227. 基本计算器 II	中等	无括号但有优先级，考察乘除先算的栈式处理
772. 基本计算器 III	困难	优先级与括号并存，最适合用分层的递归下降写
736. Lisp 语法解析	困难	前缀语法还引入变量作用域，递归时要传递环境
726. 原子的数量	困难	递归返回的是计数映射而非单值，还需按字典序输出
1096. 花括号展开 II	困难	递归返回集合，需要实现并集与笛卡尔积两种合并
385. 迷你语法分析器	中等	解析嵌套列表结构，考察整数与子列表的分支判断
241. 为运算表达式设计优先级	中等	按运算符分割做分治，返回的是所有可能结果的集合