Re: [閒聊] 每日leetcode
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的解法感覺不太直覺==
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729448723.A.8FE.html
討論串 (同標題文章)
完整討論串 (本文為第 1015 之 1554 篇)：