回归主线。
来一道稍稍麻烦的常规算法题。
题目描述
平台：LeetCode
题号：1106
给你一个以字符串形式表述的 布尔表达式 （boolean） expression，返回该式的运算结果。
有效的表达式需遵循以下约定：
"t"，运算结果为True"f"，运算结果为False"!(expr)"，运算过程为对内部表达式expr进行逻辑 非的运算（NOT）"&(expr1,expr2,...)"，运算过程为对2个或以上内部表达式expr1, expr2, ...进行逻辑 与的运算（AND）"|(expr1,expr2,...)"，运算过程为对2个或以上内部表达式expr1, expr2, ...进行逻辑 或的运算（OR）
示例 1：
代码语言：javascript复制输入：expression = "!(f)"
输出：true
示例 2：
代码语言：javascript复制输入：expression = "|(f,t)"
输出：true
示例 3：
代码语言：javascript复制输入：expression = "&(t,f)"
输出：false
示例 4：
代码语言：javascript复制输入：expression = "|(&(t,f,t),!(t))"
输出：false
提示：
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 代码：
代码语言：javascript复制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';
}
}
C 代码：
代码语言：javascript复制class Solution {
public:
bool parseBoolExpr(string s) {
deque<char> nums, ops;
for (char c : s) {
if (c == ',') continue;
if (c == 't' || c == 'f') nums.push_back(c);
if (c == '|' || c == '&' || c == '!') ops.push_back(c);
if (c == '(') nums.push_back('-');
if (c == ')') {
char op = ops.back(); ops.pop_back();
char cur = ' ';
while (!nums.empty() && nums.back() != '-') {
char top = nums.back(); nums.pop_back();
cur = cur == ' ' ? top : calc(top, cur, op);
}
if (op == '!') cur = cur == 't' ? 'f' : 't';
nums.pop_back(); nums.push_back(cur);
}
}
return nums.back() == 't';
}
char calc(char a, char b, char op) {
bool x = a == 't', y = b == 't';
bool ans = op == '|' ? x | y : x & y;
return ans ? 't' : 'f';
}
};
Python 代码：
代码语言：javascript复制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'
TypeScript 代码：
代码语言：javascript复制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'
}
- 时间复杂度：
- 空间复杂度：
