题目
题目要求
思路：栈【计算器】
- 和计算器原理类似，分别用两个栈存操作数和操作符，然后到
)就开始运算前面的内容，括号里运算都相同所以还是比较简单的。 - 要注意字母t、f和布尔值
true、false的转换。
Java
class Solution {
public boolean parseBoolExpr(String expression) {
Deque<Character> tfs = new ArrayDeque<>(), opts = new ArrayDeque<>();
for (char c : expression.toCharArray()) {
if (c == ',')
continue;
else if (c == 't' || c == 'f' || c == '(')
tfs.addLast(c);
else if (c == '|' || c == '&' || c == '!')
opts.addLast(c);
else if (c == ')') {
char op = opts.pollLast(), cur = ' ';
while (!tfs.isEmpty() && tfs.peekLast() != '(') {
char top = tfs.pollLast();
cur = cur == ' ' ? top : calBool(top, cur, op);
}
if (op == '!')
cur = cur == 't' ? 'f' : 't';
tfs.pollLast();
tfs.addLast(cur);
}
}
return tfs.peekLast() == 't';
}
char calBool(char cx, char cy, char op) {
boolean bx = cx == 't', by = cy == 't';
boolean res = op == '|' ? bx | by : bx & by;
return res ? 't' : 'f';
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(n)
C++
class Solution {
public:
bool parseBoolExpr(string expression) {
stack<char> tfs, opts;
for (auto c : expression) {
if (c == ',')
continue;
else if (c == 't' || c == 'f' || c == '(')
tfs.push(c);
else if (c == '|' || c == '&' || c == '!')
opts.push(c);
else if (c == ')') {
char op = opts.top(), cur = ' ';
opts.pop();
while (!tfs.empty() && tfs.top() != '(') {
char top = tfs.top();
tfs.pop();
cur = cur == ' ' ? top : calBool(top, cur, op);
}
if (op == '!')
cur = cur == 't' ? 'f' : 't';
tfs.pop();
tfs.push(cur);
}
}
return tfs.top() == 't';
}
char calBool(char cx, char cy, char op) {
bool bx = cx == 't', by = cy == 't';
bool res = op == '|' ? bx | by : bx & by;
return res ? 't' : 'f';
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
Rust
impl Solution {
pub fn parse_bool_expr(expression: String) -> bool {
let (mut tfs, mut opts) = (vec![], vec![]);
for c in expression.chars() {
if c == 't' || c == 'f' || c == '(' {
tfs.push(c);
}
else if c == '|' || c == '&' || c == '!' {
opts.push(c);
}
else if c == ')' {
let op = opts.pop().unwrap();
let mut cur = 'e';
while !tfs.is_empty() && tfs[tfs.len() - 1] != '(' {
let top = tfs.pop().unwrap();
if cur == 'e' {
cur = top;
}
else { // fn calBool()
let (bx, by, mut tmp) = (top == 't', cur == 't', false);
if op == '|' {
tmp = bx | by;
}
else {
tmp = bx & by;
}
if tmp {
cur = 't';
}
else {
cur = 'f';
}
}
}
if op == '!' { // 非
if cur == 't' {
cur = 'f';
}
else {
cur = 't';
}
}
tfs.pop();
tfs.push(cur);
}
}
tfs.pop().unwrap() == 't'
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(n)
总结
- 像是数据结构里学栈时举的计算器的例子，就循着这个思路感觉不算困难题。
- 当然也可以递归或者只用一个栈，整体思路其实就是巧妙一点的模拟。
以上就是Java C++刷题leetcode1106解析布尔表达式的详细内容，更多关于Java C++解析布尔表达式的资料请关注编程网其它相关文章！
