题目描述
布尔表达式 是计算结果不是 true 就是 false 的表达式。有效的表达式需遵循以下约定：
't'，运算结果为 true'f'，运算结果为 false'!(subExpr)'，运算过程为对内部表达式 subExpr 进行 逻辑非（NOT）运算'&(subExpr1, subExpr2, ..., subExprn)'，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, ..., subExprn 进行 逻辑与（AND）运算'|(subExpr1, subExpr2, ..., subExprn)'，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, ..., subExprn 进行 逻辑或（OR）运算
给你一个以字符串形式表述的 布尔表达式 expression，返回该式的运算结果。
题目测试用例所给出的表达式均为有效的布尔表达式，遵循上述约定。
示例 1：
输入：expression = "&(|(f))"
输出：false
解释：
首先，计算 |(f) --> f ，表达式变为 "&(f)" 。
接着，计算 &(f) --> f ，表达式变为 "f" 。
最后，返回 false 。
示例 2：
输入：expression = "|(f,f,f,t)"
输出：true
解释：计算 (false OR false OR false OR true) ，结果为 true 。
示例 3：
输入：expression = "!(&(f,t))"
输出：true
解释：
首先，计算 &(f,t) --> (false AND true) --> false --> f ，表达式变为 "!(f)" 。
接着，计算 !(f) --> NOT false --> true ，返回 true 。
提示：
1 <= expression.length <= 2 * 104expression[i] 为 '('、')'、'&'、'|'、'!'、't'、'f' 和 ',' 之一
解法
方法一：栈
对于这种表达式解析问题，我们可以使用栈来辅助解决。
从左到右遍历表达式 expression，对于遍历到的每个字符 $c$：
- 如果 $c$ 是
"tf!&|" 中的一个，我们直接将其入栈；
- 如果 $c$ 是右括号
')'，我们将栈中元素依次出栈，直到遇到操作符 '!' 或 '&' 或 '|'。过程中我们用变量 $t$ 和 $f$ 记录出栈字符中 't' 和 'f' 的个数。最后根据出栈字符的个数和操作符计算得到新的字符 't' 或 'f'，并将其入栈。
遍历完表达式 expression 后，栈中只剩下一个字符，如果是 't'，返回 true，否则返回 false。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是表达式 expression 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution:
def parseBoolExpr(self, expression: str) -> bool:
stk = []
for c in expression:
if c in 'tf!&|':
stk.append(c)
elif c == ')':
t = f = 0
while stk[-1] in 'tf':
t += stk[-1] == 't'
f += stk[-1] == 'f'
stk.pop()
match stk.pop():
case '!':
c = 't' if f else 'f'
case '&':
c = 'f' if f else 't'
case '|':
c = 't' if t else 'f'
stk.append(c)
return stk[0] == 't'
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
public boolean parseBoolExpr(String expression) {
Deque<Character> stk = new ArrayDeque<>();
for (char c : expression.toCharArray()) {
if (c != '(' && c != ')' && c != ',') {
stk.push(c);
} else if (c == ')') {
int t = 0, f = 0;
while (stk.peek() == 't' || stk.peek() == 'f') {
t += stk.peek() == 't' ? 1 : 0;
f += stk.peek() == 'f' ? 1 : 0;
stk.pop();
}
char op = stk.pop();
c = 'f';
if ((op == '!' && f > 0) || (op == '&' && f == 0) || (op == '|' && t > 0)) {
c = 't';
}
stk.push(c);
}
}
return stk.peek() == 't';
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | class Solution {
public:
bool parseBoolExpr(string expression) {
stack<char> stk;
for (char c : expression) {
if (c != '(' && c != ')' && c != ',')
stk.push(c);
else if (c == ')') {
int t = 0, f = 0;
while (stk.top() == 't' || stk.top() == 'f') {
t += stk.top() == 't';
f += stk.top() == 'f';
stk.pop();
}
char op = stk.top();
stk.pop();
if (op == '!') c = f ? 't' : 'f';
if (op == '&') c = f ? 'f' : 't';
if (op == '|') c = t ? 't' : 'f';
stk.push(c);
}
}
return stk.top() == 't';
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | func parseBoolExpr(expression string) bool {
stk := []rune{}
for _, c := range expression {
if c != '(' && c != ')' && c != ',' {
stk = append(stk, c)
} else if c == ')' {
var t, f int
for stk[len(stk)-1] == 't' || stk[len(stk)-1] == 'f' {
if stk[len(stk)-1] == 't' {
t++
} else {
f++
}
stk = stk[:len(stk)-1]
}
op := stk[len(stk)-1]
stk = stk[:len(stk)-1]
c = 'f'
if (op == '!' && f > 0) || (op == '&' && f == 0) || (op == '|' && t > 0) {
c = 't'
}
stk = append(stk, c)
}
}
return stk[0] == 't'
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | function parseBoolExpr(expression: string): boolean {
const expr = expression;
const n = expr.length;
let i = 0;
const dfs = () => {
let res: boolean[] = [];
while (i < n) {
const c = expr[i++];
if (c === ')') {
break;
}
if (c === '!') {
res.push(!dfs()[0]);
} else if (c === '|') {
res.push(dfs().some(v => v));
} else if (c === '&') {
res.push(dfs().every(v => v));
} else if (c === 't') {
res.push(true);
} else if (c === 'f') {
res.push(false);
}
}
return res;
};
return dfs()[0];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | impl Solution {
fn dfs(i: &mut usize, expr: &[u8]) -> Vec<bool> {
let n = expr.len();
let mut res = Vec::new();
while *i < n {
let c = expr[*i];
*i += 1;
match c {
b')' => {
break;
}
b't' => {
res.push(true);
}
b'f' => {
res.push(false);
}
b'!' => {
res.push(!Self::dfs(i, expr)[0]);
}
b'&' => {
res.push(Self::dfs(i, expr).iter().all(|v| *v));
}
b'|' => {
res.push(Self::dfs(i, expr).iter().any(|v| *v));
}
_ => {}
}
}
res
}
pub fn parse_bool_expr(expression: String) -> bool {
let expr = expression.as_bytes();
let mut i = 0;
Self::dfs(&mut i, expr)[0]
}
}
|