共计 3049 个字符,预计需要花费 8 分钟才能阅读完成。
题目形容
这是 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 多平台公布