[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


<<:  <Day28>Network-OkHttp

>>:  Microflows的Java升级版

[FGL] 可连结资料库的种类与连线方法

既然是从 INFORMIX 剥离出来的工具,应该连结资料库的能力是强大的。本段落我们检视一下Gene...

【从零开始的Swift开发心路历程-Day17】简易订单系统Part1

昨天安装完Realm之後,今天我们来实做一个简易的订单系统吧!透过TextField及Button新...

电子书阅读器上的浏览器 [Day27] 无痕模式

原先的 browser 实作就已经包含了无痕模式的细部功能,像是禁止使用 Cookie,和不记录浏览...

[30天 Vue学好学满 DAY7] 监听器(Watch)

Watch 监听器 具比较传(old & new) 无回传值(return) 监听变数发生异...

Day 16 JavaScript boxing vs unboxing

boxing: 封装可以让原始型态的资料暂时转成物件,这样他才可以使用属性或方法。 遇到使用字面值(...