【LeetCode】Day175-解析布尔表达式

题目

1106. 解析布尔表达式【困难】

题解

类比四则运算表达式，用栈来解决

如果当前字符是：

• ‘，’：跳过
• ‘，’和 ‘）’外的其他字符：入栈
• ‘）’：意味着表达式结束，将解析结果入栈
  1、栈内字符依次出栈，直到栈顶为左括号，然后将左括号和运算符弹出，记录弹出的“t”和“f”个数
  2、根据运算符以及“t”和“f”的个数计算表达式的值，并将表达式的值添加到栈内：
  如果运算符是‘！（逻辑非）’，表达式的值为括号内的值取反，f 数目为1时结果为 t ，否则为 f
  如果运算符是‘&（逻辑与）’，括号内所有值都是 t 结果为 t ，否则为 f
  如果运算符是‘|（逻辑或）’，括号内有一个值为 t ，结果为 t ，否则为 f

遍历结束后，栈内只有一个字符，t 或者 f，根据该字符返回结果

class Solution {
    public boolean parseBoolExpr(String expression) {
        int n=expression.length();
        Deque<Character>stack=new ArrayDeque<>();
        for(int i=0;i<n;i++){
            char ch=expression.charAt(i);
            //跳过逗号
            if(ch==',')
                continue;
            //遇到右括号
            else if(ch==')'){
                int t=0,f=0;
                //计算括号内t和f数目
                while(!stack.isEmpty()&&stack.peek()!='('){
                    char tmp=stack.poll();
                    if(tmp=='t')    t++;
                    else    f++;
                }
                stack.poll();//弹出左括号
                char op=stack.poll();//弹出运算符
                //根据运算符判断表达式结果，并存入栈中
                if(op=='!'){
                    if(f>0) stack.push('t');
                    else    stack.push('f');
                }
                else if(op=='&'){
                    if(f>0) stack.push('f');
                    else    stack.push('t');
                }
                else if(op=='|'){
                    if(t>0) stack.push('t');
                    else    stack.push('f');
                }
            }
            //其他符号入栈
            else
                stack.push(ch);
        }
        return stack.poll()=='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
29
30
31
32
33
34
35
36
37
38
39
40
41

这题根据思路代码还是很简单的，自己ac了~

时间复杂度：$O(n)$

空间复杂度：$O(n)$

ps. 今天居然刷到了某同学的leetcode，有760+道了，太强了，士别三日当刮目相待了