// 运算符：与、或、非
// 值：真、假

class Solution {
public:
    bool parseBoolExpr(string expression) {
        int s = 0; // 递归开始的位置
        return parseBoolExpr(expression, s);
    }

private:
    bool parseBoolExpr(string exp, int &s) {
        char ch = exp[s++]; // s++ 跳过当前字符

        if(ch == 't') return true;
        if(ch == 'f') return false;

        // 非运算
        if(ch == '!') {
            bool ans = !parseBoolExpr(exp, ++s); // 跳过左括号
            ++s;                                 // 跳过右括号
            return ans;
        }

        // 与运算 或运算
        bool isAnd = (ch == '&');       // 如果是与运算
        bool ans = isAnd;
        ++s;                            // 跳过运算符
        while(true) {
            if(isAnd)                   // 与运算
                ans &= parseBoolExpr(exp, s);
            else                        // 或运算
                ans |= parseBoolExpr(exp, s);
            if(exp[s++] == ')')         // 如果是右括号，退出
                break;
            // 如果是逗号，继续处理
        }
        return ans;
    }
};