学院打卡第十四天

今天是一道困难题，难得有困难题！！

如题：

但是这个困难题感觉也不是很”困难“！！！

算法思想：

第一感觉就是利用栈的思想，这种题做多了，一看见就是想到栈！！！果然真行！！！

---初始化2个栈，一个symbol装运算符！，&，|。一个nums装括号以及t，f。

---然后遍历字符串

---当遇到逗号  ，  直接跳过 

---遇到运算符，直接装入symbol

---当遇到   （   、 t、    和  f  直接装入nums栈中，t和f要分别转换为True和False装入！

----遇到右括号 ）   就要分情况讨论了！！！！

               （1）symbol栈出一个元素，如果是 ！，那么nums肯定只要出一个字符和左括号进行not 运算

                （2）如果是&则定义num初始值为True，如果是|则定义初始值为False，然后对nums进行出栈操作直到栈顶为左括号，每出来一个与num进行对应的运算并且重新赋值给num

                （3）最后把左括号出栈，把得出的结果num再入栈

---结束循环的时候，返回nums中的第一个元素（也只剩一个元素了！）

代码：（有一些细节在代码注释里提到！）

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        nums, symbols = [], []
        for i in expression:
            if i == "&" or i == "|" or i == "!":
                symbols.append(i)
            elif i == ",":
                continue
            else:
                if i == ")":
                    sym = symbols.pop()#先得出运算符
                    if sym=="!":
                        num=not nums.pop()
                    elif sym=="&":
                        num=True
                        while len(nums)!=0 and nums[-1]!="(":
                            num=nums.pop() and num#nums.pop()要放前面，防止num是false直接跳过nums.pop（）进入死循环！
                    else:
                        num=False
                        while len(nums)!=0 and nums[-1]!="(":
                            num=nums.pop() or num #nums.pop()要放前面，防止num是true直接没有去nums.pop()进入死循环！！！！
                    nums.pop()#左括号出栈
                    nums.append(num)#结果入栈
                else:
                    if i=="f":
                        nums.append(False)
                    elif i=="t":
                        nums.append(True)
                    else:
                        nums.append(i)
        return nums[0]

运行结果：

今天的打卡完成啦！！！