题目地址：

https://leetcode.com/problems/parsing-a-boolean-expression/

给定一个表达式，该表达式是个类似于前缀表达式的布尔表达式，其中't'代表true，'f'代表false，其定义是递归的：
1、单个't'或者'f'是个表达式；
2、如果expr是个表达式，则'!(expr)'，'&(expr,expr,...)'和'|(expr,expr,...)'都是个表达式。
求该表达式的值。

思路和表达式求值类似，只不过这里不需要考虑优先级的问题。开两个栈，一个存操作数（即't'和'f'）以及左括号'('（这是因为要标记一下做运算的操作数是哪些），另一个存操作符（即'!'，'&'和'|'）。遇到逗号则直接跳过。遇到右括号的时候开始计算，先pop出操作符和一个操作数，如果操作符是'!'，则直接将那个操作数取非入操作数栈（当然要先把左括号pop掉再入栈）；如果操作符是另外两个，则将操作数的最上面的左括号之上的所有数进行那个运算，再pop出左括号，再将计算结果入栈。最后操作数栈内就保存了运算答案。代码如下：

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    public boolean parseBoolExpr(String expression) {
        Deque<Character> ops = new ArrayDeque<>(), stk = new ArrayDeque<>();
        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);
            if (ch == ',') {
                continue;
            }
            
            if (ch == '&' || ch == '|' || ch == '!') {
                ops.push(ch);
            } else if (ch == '(' || ch == 't' || ch == 'f') {
                stk.push(ch);
            } else {
                // ch == ')'
                char op = ops.pop(), x = stk.pop();
                if (op == '!') {
                    stk.pop();
                    stk.push(x == 't' ? 'f' : 't');
                } else {
                    boolean cur = x == 't';
                    while (stk.peek() != '(') {
                        if (op == '&') {
                            cur &= stk.pop() == 't';
                        } else {
                            cur |= stk.pop() == 't';
                        }
                    }
                    
                    // pop掉左括号
                    stk.pop();
                    stk.push(cur ? 't' : 'f');
                }
            }
        }
        
        return stk.peek() == 't';
    }
}

时空复杂度$O(n)$，$n$是表达式长度。