解析布尔表达式【LC1106】
A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes:
- 't' that evaluates to true.
- 'f' that evaluates to false.
- '!(subExpr)' that evaluates to the logical NOT of the inner expression subExpr.
- '&(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical AND of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.
- '|(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical OR of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.
Given a string expression that represents a boolean expression, return the evaluation of that expression.
It is guaranteed that the given expression is valid and follows the given rules.
给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。
有效的表达式需遵循以下约定：
- "t"，运算结果为 True
- "f"，运算结果为 False
- "!(expr)"，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
- "&(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 与的运算（AND）
- "|(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 或的运算（OR）
比昨天的简单呐
两个栈
- 思路：
。构建两个栈，分别存放运算符（!、&、|）以及布尔值和左括号（(、t、f），然后模拟布尔运算
。遇到右括号时，将运算符弹出，并将左括号内的布尔值弹出，进行相应的运算，最后将该次结果保存在栈内
。最终结果即为栈顶元素
- 实现
。注意：与和或操作为多元运算符，需要记录上次的结果，
初始变量时：或运算初始值为假不影响最终结果，与运算初始值为真不影响最终结果
class Solution { public boolean parseBoolExpr(String expression) { Deque<Character> stTf = new LinkedList<>(); Deque<Character> stOpera = new LinkedList<>(); for (int i = 0; i < expression.length(); i++){ char c = expression.charAt(i); if (c == ','){ continue; }else if (c == '(' || c == 't' || c == 'f'){ stTf.addFirst(c); }else if (c == '!' || c == '&' || c == '|' ){ stOpera.addFirst(c); }else if (c == ')'){ // 进行运算 char opera = stOpera.pollFirst(); // 或运算初始值为假不影响结果 与运算初始值为真不影响结果 boolean tmp = opera == '|' ? false : true; while (stTf.peekFirst() != '('){ boolean flag = stTf.pollFirst() == 't' ? true : false; if (opera == '|'){ tmp = tmp || flag; }else if ( opera == '!'){ tmp = !flag; }else { tmp = tmp && flag; } } stTf.pollFirst(); stTf.addFirst(tmp ? 't' : 'f'); } } return stTf.pollFirst() == 't' ? true : false; } }
- 复杂度
。时间复杂度：O(n)
。空间复杂度：O(n)
一个栈
- 思路：
。单个运算表达式的结果取决于运算符以及括号内t和f的个数，因此可以使用一个栈解决该问题
- 如果运算符是 ‘!’，当f的个数为1时表达式的值为‘t’
- 如果运算符是 ‘&’，当f的个数为0时表达式的值为‘t’
- 如果运算符是 ‘|’，当t的个数大于0时表达式的值为‘t’
- 实现
1.构建一个栈，存放运算符（!、&、|）以及布尔值和左括号（(、t、f），然后模拟布尔运算
2.字符串遇到右括号时，将栈内左括号内的‘t’和‘f’弹出，并统计其个数
3.栈内遇到左括号时，将其弹出，并记录其下一个元素【运算符】
4.根据规律计算结果，并将其压入栈中
5.最终结果即为栈顶元素
- 代码
class Solution { public boolean parseBoolExpr(String expression) { Deque<Character> st = new LinkedList<>(); for (int i = 0; i < expression.length(); i++){ char c = expression.charAt(i); if (c == ','){ continue; }else if (c != ')' ){ st.addFirst(c); }else { // 统计t和f的个数 int t = 0, f = 0; while (st.peekFirst() != '('){ if (st.pollFirst() == 't'){ t++; }else{ f++; } } st.pollFirst(); char opera = st.pollFirst(); // 根据运算符进行运算 if (opera == '!'){ if (f == 1){ st.addFirst('t'); }else{ st.addFirst('f'); } }else if (opera == '&'){ if (f == 0){ st.addFirst('t'); }else{ st.addFirst('f'); } }else{ if (t > 0){ st.addFirst('t'); }else{ st.addFirst('f'); } } } } return st.pollFirst() == 't' ? true : false; } }
- 复杂度
。时间复杂度：O(n)
。空间复杂度：O(n)
