20. 有效的括号 - 力扣（LeetCode）

解题思路

一共三种情况：左括号多了，左右不匹配，右括号多了；左括号变成右括号的样子先入栈，等遍历到右括号的时候就可以直接消掉了

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []

        for ch in s:
            if ch == '(':
                stack.append(')')
            elif ch == '[':
                stack.append(']')
            elif ch =='{':
                stack.append('}')
            elif stack == [] or stack[-1] !=ch: #判断右边多和不匹配
                return False
            else:
                stack.pop()

        if stack == []:# 判断左边括号多
            return True
        else:
            return False

方法二 双指针 很绝

代码随想录 (programmercarl.com)

class Solution(object):
    def removeDuplicates(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 双指针
        slow = fast = 0
        s = list(s)
        
        while fast < len(s):
            s[slow] = s[fast]

            if slow>0 and s[slow] == s[slow-1]: #如果和前一个一样，退一个指针
                slow -= 1
            else:
                slow += 1

            fast += 1

        return "".join(s[:slow])

• 指针也可以回退

150. 逆波兰表达式求值 - 力扣（LeetCode）

解题思路

从头到尾遍历，数字压入栈，遇到运算符就pop出两个元素做运算，得到结果再压入栈，最后pop出栈中最后一个元素

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        op_map = {'+':add, '-':sub, '*':mul, '/':lambda x, y: int(x/float(y))}
       
        stack = []

        for ch in tokens:
            if ch not in op_map:
                stack.append(int(ch))
            else:
                op2 = stack.pop()
                op1 = stack.pop()
                stack.append(op_map[ch](op1,op2))
        return stack.pop()

• 有几个坑注意
  1、数字元素要变成int型
  

  2、python中除法：
  image.png