题目地址:
https://leetcode.com/problems/parsing-a-boolean-expression/
给定一个表达式,该表达式是个类似于前缀表达式的布尔表达式,其中't'
代表true,'f'
代表false,其定义是递归的:
1、单个't'
或者'f'
是个表达式;
2、如果expr
是个表达式,则'!(expr)'
,'&(expr,expr,...)'
和'|(expr,expr,...)'
都是个表达式。
求该表达式的值。
思路和表达式求值类似,只不过这里不需要考虑优先级的问题。开两个栈,一个存操作数(即't'
和'f'
)以及左括号'('
(这是因为要标记一下做运算的操作数是哪些),另一个存操作符(即'!'
,'&'
和'|'
)。遇到逗号则直接跳过。遇到右括号的时候开始计算,先pop出操作符和一个操作数,如果操作符是'!'
,则直接将那个操作数取非入操作数栈(当然要先把左括号pop掉再入栈);如果操作符是另外两个,则将操作数的最上面的左括号之上的所有数进行那个运算,再pop出左括号,再将计算结果入栈。最后操作数栈内就保存了运算答案。代码如下:
import java.util.ArrayDeque;
import java.util.Deque;
public class Solution {
public boolean parseBoolExpr(String expression) {
Deque<Character> ops = new ArrayDeque<>(), stk = new ArrayDeque<>();
for (int i = 0; i < expression.length(); i++) {
char ch = expression.charAt(i);
if (ch == ',') {
continue;
}
if (ch == '&' || ch == '|' || ch == '!') {
ops.push(ch);
} else if (ch == '(' || ch == 't' || ch == 'f') {
stk.push(ch);
} else {
// ch == ')'
char op = ops.pop(), x = stk.pop();
if (op == '!') {
stk.pop();
stk.push(x == 't' ? 'f' : 't');
} else {
boolean cur = x == 't';
while (stk.peek() != '(') {
if (op == '&') {
cur &= stk.pop() == 't';
} else {
cur |= stk.pop() == 't';
}
}
// pop掉左括号
stk.pop();
stk.push(cur ? 't' : 'f');
}
}
}
return stk.peek() == 't';
}
}
时空复杂度 O ( n ) O(n) O(n), n n n是表达式长度。