LeetCode:1106. 解析布尔表达式

题目描述

链接 https://leetcode.cn/problems/parsing-a-boolean-expression/description/

解题思路

分析题目可以知道，需要使用栈这个数据结构存储expression这个字符串中的字符。
从左到右遍历布尔表达式，对于每种类型的字符，执行相应的操作：

• 如果当前字符是逗号，则跳过该字符；

• 如果当前字符是除了逗号和右括号以外的任意字符，则将该字符添加到栈内；

• 如果当前字符是右括号，则一个表达式遍历结束，需要解析该表达式的值，并将结果添加到栈内：

  • 将栈内字符依次弹出，直到栈顶字符是左括号，然后将左括号和运算符从栈内弹出，记录弹出的 t和 f 的个数；
  • 取出栈顶的运算符字符，根据t和f的数量，将新的结果入栈

• 最后栈中剩余的字符即是结构

代码

public boolean parseBoolExpr(String expression) {
        Deque<Character> stack = new LinkedList<>();
        for(int i = 0; i < expression.length(); i++){
            char c = expression.charAt(i);
            if(c == ','){
                continue;
            }else if(c != ')'){
                stack.push(c);
            }else{
                int t = 0, f = 0;
                while(stack.peek() != '('){
                    char val = stack.pop();
                    if(val == 't'){
                        t++;
                    }else{
                        f++;
                    }
                }
                // ( 弹出
                stack.pop();
                // 弹出操作数，并且进行判断和就算，将新的结果添加到栈中
                char op = stack.pop();
                switch(op){
                    case '!':
                        stack.push(f == 1 ? 't' : 'f');
                        break;
                    case '&':
                        stack.push(f == 0 ? 't' : 'f');
                        break;
                    case '|':
                        stack.push(t > 0 ? 't' : 'f');
                        break;
                    default:
                }
            }
        }
        return stack.pop() == 't' ? true : false;
    }
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