【115】

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.如果是逗号则跳过；
　　2.如果是左括号，运算符或者't','f'，则入栈；
　　3.如果是右括号，则需要返回一对括号里的内容：将栈内元素依次弹出，直到栈顶元素为左括号为止，然后将左括号和运算符弹出，记录弹出元素中't'和'f'的数量。
根据运算符以及弹出't','f'的数量计算一对括号里的值：
　　1.如果运算符是'!',将括号内的值取反；
　　2.如果运算符是'&',如果括号内所有元素都是't'，则结果是't',否则结果是'f'，即如果'f'的个数为0，返回't'，否则返回'f'；
　　3.如果运算符是'|',如果括号内't'的个数不为0时，返回't'，否则返回'f'。

 1 class Solution {
 2     public boolean parseBoolExpr(String expression) {
 3         Deque<Character> stack = new ArrayDeque<>();
 4         for(int i = 0; i < expression.length(); i++){
 5             char ch = expression.charAt(i);
 6             if(ch == ','){
 7                 continue;
 8             }else if(ch != ')'){
 9                 stack.push(ch);
10             }else{
11                 int t = 0, f = 0;
12                 while(stack.peek() != '('){
13                     char value = stack.pop();
14                     if(value == 't'){
15                         t++;
16                     }else{
17                         f++;
18                     }
19                 }
20                 stack.pop();
21                 char symbol = stack.pop();
22                 if(symbol == '!'){
23                     stack.push(t == 1 ? 'f':'t');
24                 }else if(symbol == '&'){
25                     stack.push(f == 0 ? 't':'f');
26                 }else{
27                     stack.push(t != 0 ? 't':'f');
28                 }
29             }
30         }
31         return stack.pop() == 't';
32     }
33 }