栈题目：解析布尔表达式

题目

标题和出处

标题：解析布尔表达式

出处：1106. 解析布尔表达式

难度

6 级

题目描述

要求

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

有效的表达式需遵循以下约定：

• $\text{"t"}$，运算结果为 $\text{True}$；
• $\text{"f"}$，运算结果为 $\text{False}$；
• $\text{"!(expr)"}$，运算过程为对内部表达式 $\text{expr}$ 进行逻辑非的运算；
• $\text{"\&(expr1,expr2,…)"}$，运算过程为对 $\text{2}$ 个或以上内部表达式 $\text{expr1, expr2, …}$ 进行逻辑与的运算；
• $\text{"|(expr1,expr2,…)"}$，运算过程为对 $\text{2}$ 个或以上内部表达式 $\text{expr1, expr2, …}$ 进行逻辑或的运算。

示例

示例 1：

输入：$\text{expression = "!(f)"}$
输出：$\text{true}$

示例 2：

输入：$\text{expression = "|(f,t)"}$
输出：$\text{true}$

示例 3：

输入：$\text{expression = "\&(t,f)"}$
输出：$\text{false}$

示例 4：

输入：$\text{expression = "|(\&(t,f,t),!(t))"}$
输出：$\text{false}$

数据范围

• $\text{1}\le \text{expression.length}\le \text{20000}$
• $\text{expression}$ 由 $\text{{‘(’, ‘)’, ‘\&’, ‘|’, ‘!’, ‘t’, ‘f’, ‘,’}}$ 中的字符组成
• $\text{expression}$ 是以上述形式给出的有效表达式，表示一个布尔值

解法

思路和算法

布尔表达式中，每个逻辑运算符（与、或、非）都对后面的一对括号内的内部表达式进行运算。由于需要根据每一对匹配的括号进行解析和运算，寻找匹配的括号需要借助栈的数据结构，因此可以使用栈实现解析布尔表达式。

由于布尔表达式中的逗号的作用是分隔内部表达式，并不影响布尔表达式的结果，因此可以跳过逗号，只对非括号字符解析和运算。

从左到右遍历布尔表达式 $\text{expression}$，遇到非括号且非右括号的字符则入栈，遇到右括号则开始解析，解析过程如下。

1. 将栈内的元素依次出栈，直到遇到左括号，计算出栈的 $\text{‘t’}$ 和 $\text{‘f’}$ 的个数。

2. 将左括号出栈，然后将逻辑运算符出栈。

3. 根据逻辑运算符计算当前内部表达式的值：

   • 如果逻辑运算符是 $\text{‘\&’}$，则是逻辑与运算，当 $\text{‘f’}$ 的个数等于 $0$ 时，内部表达式的值为 $\text{‘t’}$，否则内部表达式的值为 $\text{‘f’}$。

   • 如果逻辑运算符是 $\text{‘|’}$，则是逻辑或运算，当 $\text{‘t’}$ 的个数大于 $0$ 时，内部表达式的值为 $\text{‘t’}$，否则内部表达式的值为 $\text{‘f’}$。

   • 如果逻辑运算符是 $\text{‘!’}$，则是逻辑非运算，当 $\text{‘f’}$ 的个数大于 $0$ 时，内部表达式的值为 $\text{‘t’}$，否则内部表达式的值为 $\text{‘f’}$。

4. 将内部表达式的值入栈。

重复上述操作，直到遍历完毕布尔表达式。

由于 $\text{expression}$ 是有效的布尔表达式，因此一定能正确解析，遍历结束时，栈内只有一个元素，为布尔表达式的结果。如果栈内的元素是 $\text{‘t’}$，返回 $\text{true}$，否则返回 $\text{false}$。

代码

class Solution {
    
    public boolean parseBoolExpr(String expression) {
    
        Deque<Character> stack = new ArrayDeque<Character>();
        int length = expression.length();
        for (int i = 0; i < length; i++) {
    
            char c = expression.charAt(i);
            if (c == ',') {
    
                continue;
            } else if (c == ')') {
    
                int tCount = 0, fCount = 0;
                while (stack.peek() != '(') {
    
                    char prev = stack.pop();
                    if (prev == 't') {
    
                        tCount++;
                    } else if (prev == 'f') {
    
                        fCount++;
                    }
                }
                stack.pop();
                char op = stack.pop();
                if (op == '&') {
    
                    char curr = fCount == 0 ? 't' : 'f';
                    stack.push(curr);
                } else if (op == '|') {
    
                    char curr = tCount > 0 ? 't' : 'f';
                    stack.push(curr);
                } else if (op == '!') {
    
                    char curr = fCount > 0 ? 't' : 'f';
                    stack.push(curr);
                }
            } else {
    
                stack.push(c);
            }
        }
        return stack.pop() == 't';
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是布尔表达式 $\text{expression}$ 的长度。需要遍历布尔表达式一次，每个字符最多入栈和出栈各一次。

• 空间复杂度：$O(n)$，其中 $n$ 是布尔表达式 $\text{expression}$ 的长度。空间复杂度主要取决于栈空间，栈内元素个数不会超过 $n$。