1106. 解析布尔表达式

🔴   🔖  栈 递归 字符串  🔗 力扣 LeetCode

题目

A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes:

• 't' that evaluates to true.
• 'f' that evaluates to false.
• '!(subExpr)' that evaluates to the logical NOT of the inner expression subExpr.
• '&(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical AND of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.
• '|(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical OR of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.

Given a string expression that represents a boolean expression , return the evaluation of that expression.

It is guaranteed that the given expression is valid and follows the given rules.

Example 1:

Input: expression = "&(|(f))"

Output: false

Explanation:

First, evaluate |(f) --> f. The expression is now "&(f)".

Then, evaluate &(f) --> f. The expression is now "f".

Finally, return false.

Example 2:

Input: expression = "|(f,f,f,t)"

Output: true

Explanation: The evaluation of (false OR false OR false OR true) is true.

Example 3:

Input: expression = "!(&(f,t))"

Output: true

Explanation:

First, evaluate &(f,t) --> (false AND true) --> false --> f. The expression is now "!(f)".

Then, evaluate !(f) --> NOT false --> true. We return true.

Constraints:

• 1 <= expression.length <= 2 * 10^4
• expression[i] is one following characters: '(', ')', '&', '|', '!', 't', 'f', and ','.

题目大意

布尔表达式 是计算结果不是 true 就是 false 的表达式。有效的表达式需遵循以下约定：

• 't'，运算结果为 true
• 'f'，运算结果为 false
• '!(subExpr)'，运算过程为对内部表达式 subExpr 进行 逻辑非 （NOT）运算
• '&(subExpr1, subExpr2, ..., subExprn)'，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, ..., subExprn 进行 逻辑与 （AND）运算
• '|(subExpr1, subExpr2, ..., subExprn)'，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, ..., subExprn 进行 逻辑或 （OR）运算

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

题目测试用例所给出的表达式均为有效的布尔表达式，遵循上述约定。

提示：

• 1 <= expression.length <= 2 * 10^4
• expression[i] 为 '('、')'、'&'、'|'、'!'、't'、'f' 和 ',' 之一

解题思路

利用栈来处理布尔表达式，以便处理嵌套的表达式和操作符优先级。

从左到右遍历表达式的每个字符。

• 如果字符是 ,，则跳过（不需要处理逗号）。

• 如果字符是 t 或 f，将其转换为布尔值并压入栈中。

• 如果字符是 ( 、 & 、 | 、 !，将其压入栈中。

• 如果字符是 )，则开始计算最近一个括号中的表达式，并将计算结果压入栈中：

  • 首先弹出操作数到一个数组 values，直到找到对应的左括号 (；

  • 弹出栈顶的操作符（&、| 或 !）。

  • 根据操作符进行相应的布尔运算：

    • 对于 &，使用 every 方法判断所有值是否为 true。
    • 对于 |，使用 some 方法判断是否至少有一个值为 true。
    • 对于 !，直接对第一个值取反。

  • 遍历结束后，栈中的唯一元素即为表达式的最终结果。

复杂度分析

• 时间复杂度：O(n)，其中 n 是表达式的长度。每个字符都被处理一次。
• 空间复杂度：O(n)，在最坏情况下，栈的空间复杂度为 O(n)。

代码

/**
 * @param {string} expression
 * @return {boolean}
 */
var parseBoolExpr = function (expression) {
	let stack = [];

	for (let i = 0; i < expression.length; i++) {
		const char = expression[i];
		if (char == ',') {
			continue; // 跳过逗号
		} else if (char === 't' || char === 'f') {
			stack.push(char === 't'); // 将 't' 和 'f' 转换为布尔值
		} else if (char == ')') {
			let values = [];
			while (stack.length && stack[stack.length - 1] !== '(') {
				values.push(stack.pop());
			}

			stack.pop(); // 移除 '('
			const sign = stack.pop(); // 获取操作符

			if (sign == '&') {
				stack.push(values.every(Boolean)); // 逻辑与
			} else if (sign == '|') {
				stack.push(values.some(Boolean)); // 逻辑或
			} else {
				stack.push(!values[0]); // 逻辑非
			}
		} else {
			stack.push(char); // 将括号或操作符压入栈
		}
	}
	return stack[0]; // 最终结果
};