iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 26
1
Software Development

LeetCode30系列 第 26

[LeetCode30] Day26 - 1106. Parsing A Boolean Expression

題目

給一個型別為string的boolean expression,回傳結果(true or false)
experssion包含

  1. "t" = true
  2. "f" = false
  3. "!(expr)", where expr = "f" or "t"
  4. &(expr1,expr2,...), where expr = "f" or "t"
  5. |(expr1,expr2,...), where expr = "f" or "t"
  • Example
    • &(t,f), return false
    • |(&(t,f,t),!(t)), return false

解法

  • 類似做加減乘除運算表示的解法,平常看到是中序表示法,會轉成前敘或後敘去解。

  • 那這裡我們可以看到題目的三種運算 ,,,後面一定有 ()

  • 所以我們能右往左丟進stack,當遇到3個運算符,再將前面丟的拿出來做掉,直到遇到 )

  • 逗號部分不影響,所以直接忽略即可!。

  • 基本上分不同運算去處理,就完成了

Code

class Solution {
public:
    bool parseBoolExpr(string s) {
        stack<char> stack;
        
        for(int i = s.length() - 1; i >= 0; i--){
            if(s[i] == '|'){
                bool result = false;
                while(stack.size()){
                    if(stack.top()=='('){
                        stack.pop();
                    }
                    else if(stack.top()=='t'){
                        result|=1;
                        stack.pop();
                    }
                    else if(stack.top()=='f'){
                        result|=0;
                        stack.pop();
                    }
                    else if(stack.top()==')'){
                        stack.pop();
                        stack.push(result==true?'t':'f');
                        break;
                    }
                }
            }
            else if(s[i]=='!'){
                bool result=false;
                while(stack.size()){
                    if(stack.top()=='('){
                        stack.pop();
                    }
                    else if(stack.top()=='t'){
                        result|=1;
                        stack.pop();
                    }
                    else if(stack.top()=='f'){
                        result|=0;
                        stack.pop();
                    }
                    else if(stack.top()==')'){
                        stack.pop();
                        stack.push(!result==true?'t':'f');
                        break;
                    }
                }
               
            }
            else if(s[i]=='&'){
                bool result=true;
                while(stack.size()){
                    if(stack.top()=='('){
                        stack.pop();
                    }
                    else if(stack.top()=='t'){
                        result&=1;
                        stack.pop();
                    }
                    else if(stack.top()=='f'){
                        result&=0;
                        stack.pop();
                    }
                    else if(stack.top()==')'){
                        stack.pop();
                        stack.push(result==true?'t':'f');
                        break;
                    }
                }
            }
            else if(s[i]==','){
                continue;
            }
            else{
                stack.push(s[i]);
            }
        }
        if(stack.size()){
            if(stack.top()=='t'){
                return true;
            }
            else{
                return false;
            }
        }
        return true;
    }
};

https://ithelp.ithome.com.tw/upload/images/20201007/20129147dXR131dK1T.png


上一篇
[LeetCode30] Day25 - 483. Smallest Good Base
下一篇
[LeetCode30] Day27 - 42. Trapping Rain Water
系列文
LeetCode3030
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言