20. 有效的括号

思路：列表最适合栈的结构，后加append可以先出pop

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        
        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            elif not stack or stack[-1] != item:
                return False
            else:
                stack.pop()
        
        return True if not stack else False

1047. 删除字符串中的所有相邻重复项

思路：栈用来存对称的元素，只要在主数组中发现对称的元素，就pop

class Solution:
    def removeDuplicates(self, s: str) -> str:
        ll=[]
        for i in s:
            
            if len(ll)and i==ll[-1]:
                ll.pop()
            else:
                ll.append(i)
        return ('').join(ll)

150. 逆波兰表达式求值

思路：什么是逆波兰表达式，其实是二叉树当中的后序遍历：左右中，我们看到的表达式通常为二叉树的中序遍历，左中右，但是每计算一步都要加（）区分优先级，这道题还要注意怎么将运算字符串作为运算符使用，eval速度很慢，建议使用字典

from operator import add, sub, mul

class Solution:
    op_map = {'+': add, '-': sub, '*': mul, '/': lambda x, y: int(x / y)}
    
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token not in {'+', '-', '*', '/'}:
                stack.append(int(token))
            else:
                op2 = stack.pop()
                op1 = stack.pop()
                stack.append(self.op_map[token](op1, op2))  # 第一个出来的在运算符后面
        return stack.pop()