题目描述

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

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

• "t"，运算结果为 True
• "f"，运算结果为 False
• "!(expr)"，运算过程为对内部表达式 expr 进行逻辑非的运算（NOT）
• "&(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑与的运算（AND）
• "|(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑或的运算（OR）

样例

输入：expression = "!(f)"
输出：true

输入：expression = "|(f,t)"
输出：true

输入：expression = "&(t,f)"
输出：false

输入：expression = "|(&(t,f,t),!(t))"
输出：false

限制

• 1 <= expression.length <= 20000
• expression[i] 由 {'(', ')', '&', '|', '!', 't', 'f', ','} 中的字符组成。
• expression 是以上述形式给出的有效表达式，表示一个布尔值。

算法

(递归) $O(n)$

1. 因为布尔表达式本身就是递归定义，所以我们同样可以采用递归的方式求解。
2. 递归时，需要实时维护一个位置 cur 代表当前从字符串的哪个位置开始解析。具体过程可以参考代码

时间复杂度

• 每个位置仅遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 递归需要系统栈空间，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    bool parse(const string &expression, int &cur) {
        // 需要实时维护当前位置，所以 cur 要取引用。
        if (expression[cur] == 't') {
            cur++;
            return true;
        } else if (expression[cur] == 'f') {
            cur++;
            return false;
        } else if (expression[cur] == '!') {
            cur += 2;
            bool ret = !parse(expression, cur);
            cur++;
            return ret;
        } else if (expression[cur] == '&') {
            cur += 2;
            bool ret = true;
            while (true) {
                ret &= parse(expression, cur);
                cur++;
                if (expression[cur - 1] == ')')
                    break;
            }
            return ret;
        } else {
            cur += 2;
            bool ret = false;
            while (true) {
                ret |= parse(expression, cur);
                cur++;
                if (expression[cur - 1] == ')')
                    break;
            }
            return ret;
        }
    }

    bool parseBoolExpr(string expression) {
        int cur = 0;
        return parse(expression, cur);
    }
};