LeetCode-1106. 解析布尔表达式【栈，递归，字符串】

题目描述：

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

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

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

示例 1：

输入：expression = “!(f)”
输出：true

示例 2：

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

示例 3：

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

示例 4：

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

提示：

1 <= expression.length <= 20000
expression[i] 由 {‘(’, ‘)’, ‘&’, ‘|’, ‘!’, ‘t’, ‘f’, ‘,’} 中的字符组成。
expression 是以上述形式给出的有效表达式，表示一个布尔值。
https://leetcode.cn/problems/parsing-a-boolean-expression/description/?orderBy=most_votes

解题思路一：注释清晰，简洁明了。栈，将expression分为三种情况//一：为逗号（不管）//二：非右括号（直接入栈）//三右括号（对栈内元素进行操作）

class Solution {
public:
    bool parseBoolExpr(string expression) {
        stack<char> stk;//栈
        int n=expression.size();
        for(auto c:expression){//c分为三种情况。
            if(c==',') continue;//一：为逗号
            else if(c!=')') stk.push(c);//二：非右括号
            else{//三右括号
                int t=0,f=0;
                while(stk.top()!='('){//计算t与f的个数，遇到左括号停止
                    char val=stk.top();stk.pop();
                    if(val=='t') ++t;
                    else ++f;
                }
                stk.pop();//左括号
                char op=stk.top();stk.pop();//操作符
                switch(op){
                    case '!': stk.push(f==1?'t':'f');break;//非运算符，只需判断当前结果是t还是f，然后取反即可
                    case '&': stk.push(f>0?'f':'t');break;//且
                    case '|': stk.push(t>0?'t':'f');break;//或
                    default: break;
                }                
            }
        }
        return stk.top()=='t';//最终只剩下一个符合。
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

时间复杂度：O(n)
空间复杂度：O(n)栈stk

解题思路二：0

1

解题思路三：0

1