题目形容
这是 LeetCode 上的 1106. 解析布尔表达式 ，难度为艰难。
Tag : 「栈」、「表达式计算」
给你一个以字符串模式表述的 布尔表达式 （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是以上述模式给出的无效表达式，示意一个布尔值。
双栈
为了不便，咱们令 expression 为 s。
咱们能够将 t 和 f 看做操作数，而 |、& 和 ! 看做操作符，创立两个栈 nums 和 ops 别离对其进行存储。
残余的 () 和 , 则只是优先级和分隔符，毋庸额定关注。
从前往后解决 s，依据以后解决的字符为何值进行分状况探讨：
,：分隔符，间接跳过；t或f：操作数，增加到nums栈中；|、&或!：操作符，增加到ops栈中；(：子表达式的左端点，为了在咱们从「双栈」中取出数值和符号计算时，能够晓得某个子表达式计算实现，须要记录一下。往nums追加一个占位符号-来代指；)：子表达式的右端点，代表一个子表达式的完结。可从「双栈」中取出符号和数组进行计算（在ops中仅取栈顶元素，代表以后子表达式的操作符；而在nums中则取到代表左端点的占位元素-为止），并将后果从新放入nums中。
最初思考如何计算最简表达式，思考实现一个 char calc(char a, char b, char op) 函数，代表对操作数 a 和 b 执行 op 操作并进行后果返回。
实际上，在 calc 函数咱们只辨别 | 操作和其余操作即可。也就是说 & 和 ! 均当做 & 来做，! 操作在计算残缺个表达式后再翻转。
Java 代码：
class Solution { public boolean parseBoolExpr(String s) { Deque<Character> nums = new ArrayDeque<>(), ops = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c == ',') continue; if (c == 't' || c == 'f') nums.addLast(c); if (c == '|' || c == '&' || c == '!') ops.addLast(c); if (c == '(') nums.addLast('-'); if (c == ')') { char op = ops.pollLast(), cur = ' '; while (!nums.isEmpty() && nums.peekLast() != '-') { char top = nums.pollLast(); cur = cur == ' ' ? top : calc(top, cur, op); } if (op == '!') cur = cur == 't' ? 'f' : 't'; nums.pollLast(); nums.addLast(cur); } } return nums.peekLast() == 't'; } char calc(char a, char b, char op) { boolean x = a == 't', y = b == 't'; boolean ans = op == '|' ? x | y : x & y; return ans ? 't' : 'f'; }}TypeScript 代码：
function parseBoolExpr(s: string): boolean { function calc(a: string, b: string, op: string): string { const x = a == 't', y = b == 't' const ans = op == '|' ? x || y : x && y return ans ? 't' : 'f' } const nums = new Array<string>(s.length).fill(''), ops = new Array<string>(s.length).fill('') let idx1 = 0, idx2 = 0 for (const c of s) { if (c == ',') continue if (c == 't' || c == 'f') nums[idx1++] = c if (c == '|' || c == '&' || c == '!') ops[idx2++] = c if (c == '(') nums[idx1++] = '-' if (c == ')') { let op = ops[--idx2], cur = ' ' while (idx1 > 0 && nums[idx1 - 1] != '-') { const top = nums[--idx1] cur = cur == ' ' ? top : calc(top, cur, op) } if (op == '!') cur = cur == 't' ? 'f' : 't' idx1--; nums[idx1++] = cur } } return nums[idx1 - 1] == 't'}Python 代码：
class Solution: def parseBoolExpr(self, s: str) -> bool: def calc(a, b, op): x, y = a == 't', b == 't' ans = x | y if op == '|' else x & y return 't' if ans else 'f' nums, ops = [], [] for c in s: if c == ',': continue if c == 't' or c == 'f': nums.append(c) if c == '|' or c == '&' or c == '!': ops.append(c) if c == '(': nums.append('-') if c == ')': op, cur = ops.pop(), ' ' while nums and nums[-1] != '-': top = nums.pop() cur = top if cur == ' ' else calc(cur, top, op) if op == '!': cur = 't' if cur == 'f' else 'f' nums.pop() nums.append(cur) return nums[-1] == 't'- 工夫复杂度：$O(n)$
- 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.1106 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布