Hard

题目描述

布尔表达式是一个计算结果为 true 或 false 的表达式。它可以是以下形式之一：

  • ’t’，计算结果为 true
  • ‘f’，计算结果为 false
  • ‘!(subExpr)’，计算结果为内部表达式 subExpr 的逻辑非
  • ‘&(subExpr1, subExpr2, …, subExprn)’，计算结果为内部表达式 subExpr1, subExpr2, …, subExprn 的逻辑与，其中 n >= 1
  • ‘|(subExpr1, subExpr2, …, subExprn)’，计算结果为内部表达式 subExpr1, subExpr2, …, subExprn 的逻辑或，其中 n >= 1

给你一个以字符串形式表示的布尔表达式 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 * 10^4
  • expression[i] 是 ‘(’, ‘)’, ‘&’, ‘|’, ‘!’, ’t’, ‘f’, ‘,’ 中的一个字符

解题思路

这是一个递归解析问题，可以用多种方法解决：

方法一：递归解析（推荐） 根据表达式的结构特点，我们可以设计一个递归函数来解析。当遇到操作符时，递归解析其内部的子表达式：

  • 对于 ’t’ 和 ‘f’，直接返回对应的布尔值
  • 对于 ‘!’, ‘&’, ‘|’，找到对应的括号范围，递归解析内部的子表达式
  • 使用指针跟踪当前解析位置，避免重复扫描

方法二：栈模拟 使用栈来模拟表达式的嵌套结构，从左到右扫描字符串，遇到操作符压栈，遇到右括号时弹栈计算结果。

方法三：字符串替换 反复查找最内层的表达式并计算结果，用结果替换原表达式，直到整个表达式被简化为单个字符。

递归解析方法最为直观和高效，时间复杂度为 O(n)，空间复杂度为 O(d)，其中 d 是表达式的嵌套深度。

代码实现

class Solution {
public:
    bool parseBoolExpr(string expression) {
        int index = 0;
        return parse(expression, index);
    }
    
private:
    bool parse(const string& expr, int& index) {
        char c = expr[index++];
        
        if (c == 't') return true;
        if (c == 'f') return false;
        
        if (c == '!') {
            index++; // skip '('
            bool result = !parse(expr, index);
            index++; // skip ')'
            return result;
        }
        
        if (c == '&') {
            index++; // skip '('
            bool result = true;
            while (expr[index] != ')') {
                if (expr[index] == ',') index++;
                result &= parse(expr, index);
            }
            index++; // skip ')'
            return result;
        }
        
        if (c == '|') {
            index++; // skip '('
            bool result = false;
            while (expr[index] != ')') {
                if (expr[index] == ',') index++;
                result |= parse(expr, index);
            }
            index++; // skip ')'
            return result;
        }
        
        return false;
    }
};

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        self.index = 0
        return self.parse(expression)
    
    def parse(self, expr):
        c = expr[self.index]
        self.index += 1
        
        if c == 't':
            return True
        if c == 'f':
            return False
        
        if c == '!':
            self.index += 1  # skip '('
            result = not self.parse(expr)
            self.index += 1  # skip ')'
            return result
        
        if c == '&':
            self.index += 1  # skip '('
            result = True
            while expr[self.index] != ')':
                if expr[self.index] == ',':
                    self.index += 1
                result &= self.parse(expr)
            self.index += 1  # skip ')'
            return result
        
        if c == '|':
            self.index += 1  # skip '('
            result = False
            while expr[self.index] != ')':
                if expr[self.index] == ',':
                    self.index += 1
                result |= self.parse(expr)
            self.index += 1  # skip ')'
            return result
        
        return False

public class Solution {
    private int index;
    
    public bool ParseBoolExpr(string expression) {
        index = 0;
        return Parse(expression);
    }
    
    private bool Parse(string expr) {
        char c = expr[index++];
        
        if (c == 't') return true;
        if (c == 'f') return false;
        
        if (c == '!') {
            index++; // skip '('
            bool result = !Parse(expr);
            index++; // skip ')'
            return result;
        }
        
        if (c == '&') {
            index++; // skip '('
            bool result = true;
            while (expr[index] != ')') {
                if (expr[index] == ',') index++;
                result &= Parse(expr);
            }
            index++; // skip ')'
            return result;
        }
        
        if (c == '|') {
            index++; // skip '('
            bool result = false;
            while (expr[index] != ')') {
                if (expr[index] == ',') index++;
                result |= Parse(expr);
            }
            index++; // skip ')'
            return result;
        }
        
        return false;
    }
}

var parseBoolExpr = function(expression) {
    let i = 0;
    
    function parse() {
        const char = expression[i++];
        
        if (char === 't') return true;
        if (char === 'f') return false;
        
        const op = char;
        i++; // skip '('
        
        const values = [];
        while (expression[i] !== ')') {
            if (expression[i] === ',') {
                i++;
            } else {
                values.push(parse());
            }
        }
        i++; // skip ')'
        
        if (op === '!') return !values[0];
        if (op === '&') return values.every(v => v);
        if (op === '|') return values.some(v => v);
    }
    
    return parse();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
递归解析O(n)O(d)

其中 n 是表达式的长度，d 是表达式的嵌套深度（递归调用栈的深度）。