栈

什么时候适合使用栈？涉及之前的操作，或者之前的操作无效时候、、、

leetcode 20 括号匹配！！！

总结：解题关键有两点

1. 用栈
2. 什么时候入栈出栈用 key 和 value 标识会清除太多，不然一直都绕不过弯来！！！

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        d = {"(":")", "[":"]", "{": "}"}
        stack = []
        for item in s:
            if item in d:
                key = item
                stack.append(key)
            else:
                value = item
                key = stack.pop() if stack else None
                if not key:
                    return False
                if value != d[key]:
                    return False
        return True if not stack else False

经验：栈结合新变量使用，思路会更加清晰！

leetcode 71 简化路径！！！

简化 unix 路径
思路：先把所有斜杠去掉。栈之状态机，一共有三种情况：什么时候入栈，什么时候不动，什么时候出栈，思考好了，结果就出来了！！！

class Solution(object):
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        stack = []
        temp = path.split("/")
        for s in temp:
            if s == ".." and stack:
                stack.pop()
            elif s == "." or s == "" or (s == ".." and not stack):
                continue
            else:
                stack.append(s)
        return "/" + "/".join(stack)