1106.
原本想说周赛前练个手
看到是hard就怕了==
第四题MLE很不爽
音乐节玩完回来才写
结果这题蛮简单ㄉ==
就parse expr
##结构
我开两个stack
一个放operation 一个放expression
左括号也放expr 当stop signal
空格逗点跳过不放
##跑
照顺序看string 丢进stack
看到 右括号 ) 做reduce
看op是啥 一个一个缩
缩到碰到左括号停下来
把结果再放回expr
缩完理论上就只剩一个expr
class Solution {
public:
bool parseBoolExpr(string exp) {
char op = '&';
// '&', '|', '!';
stack<char> ops;
stack<char> exps;
for(char& c: exp){
if(c == ',' or c == ' ') continue;
if(c == '!' or c == '&' or c == '|'){
ops.push(c);
}
else if( c == ')'){
if(!ops.empty()){
op = ops.top();
ops.pop();
}
bool res = true;
if(exps.top() == 'f') res = false;
while(exps.top() != '('){
char e = exps.top();
reduce(op, e, res);
exps.pop();
}
exps.pop();
if(res) exps.push('t');
else exps.push('f');
}
else exps.push(c);
}
return (exps.top() == 't') ? true : false;
}
void reduce(char& op, char& e, bool& res){
bool tf;
if(e == 't') tf = true;
else tf = false;
if(op == '&') res &= tf;
else if(op == '|') res |= tf;
else res = !tf;
}
};
看别人只开一个stack的解法感觉不太直觉==