Leetcode1106：解析布尔表达式

原文链接：1106. 解析布尔表达式 - 力扣（LeetCode）

---

题目

        给你一个以字符串形式表述的 布尔表达式（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 是以上述形式给出的有效表达式，表示一个布尔值。

解题思路

1、利用栈，存放不为,和)的元素
2、遇到 ）则将最靠上的（ 到 ）之间的元素全部弹出
      同时记录t和f的个数
3、然后根据此时栈顶元素的符号数，判断这一段的结果是什么
4、最后栈中只剩一个元素，即结果

时间：16ms 空间：41.4MB

class Solution {
    public boolean parseBoolExpr(String expression) {
		Stack stack=new Stack<>();
        for(char temp : expression.toCharArray()){
            if(temp != ',' && temp!=')'){
                stack.push(temp);
            }
            else if(temp==')'){
                //如果当前元素为右括号
                int t=0,f=0;
                //不断弹出栈顶元素，直到栈顶为左括号
                while(stack.peek()!='('){
                    char con = stack.pop();
                    //记录t和f的数量
                	if(con == 't')t++;
                    else f++;
                }
                stack.pop();//弹出'('
                //弹出并返回符号数
                char operator = stack.pop();
                if(operator=='&'){
                    //符号数是&，则判断是否存在f
                    //如果存在，结果为f，然后入栈
                    char ans = f>0?'f':'t';
                    stack.push(ans);
                }
                else if(operator=='|'){
                    //符号数是|，则判断是否存在t
                    //存在，结果为t，入栈
                    char ans = t>0?'t':'f';
                    stack.push(ans);
                }
                else{
                    //符号数是!，判断是否为t
                    //是，则取反，入栈
                    char ans = t>0?'f':'t';
                    stack.push(ans);
                }
            }
        }
        //此时栈顶只剩一个元素，判断是否为t即可
        return stack.peek()=='t';
    }
}