leetcode 20. 有效的括号(栈的解法)

题目在这:https://leetcode-cn.com/problems/valid-parentheses/

括号匹配问题，立马想到用栈去做.

遇到左括号进栈，遇到右括号匹配当前栈顶，相同就把栈顶的元素弹出，不同直接返回False

建立字典存储左右括号的对应.

有几个左括号一定有几个有括号，所以如果括号总数不是偶数，必然不对。可以先判断字符串长度是不是偶数.

上代码!

s = '{}[]}{'
hashmap = {'(':')','[':']','{':'}'}
stack = []
if len(s)%2:
    return False
for i in s:
    if i in hashmap.keys():
        stack.append(i)
    elif not stack or hashmap[stack.pop()]!=i:
        return False
if stack:
    return False
else:
    return True

代码中唯一容易错的地方解释一下：

elif not stack or hashmap[stack.pop()]!=i:

这句话的意思是：
stack这个栈里面为空则进入elif 返回False。

需要注意的点 ：

1. 给的括号是 ‘} {’ 这样的情况，先匹配到左括号，不进栈，此时栈中为空，没有括号和 ‘}‘ 相匹配。所以直接返回False
相同的情况 还有 “[]{}}{” 同理 前面的 []{} 匹配完了，后面又是直接一个 ‘}’ 没有左括号和他匹配(栈中为空),这时候直接返回False。

2, 这句话里面的 not stack 必须写到 or 前面。
如果写到后面，当栈为空的时候，执行了pop会直接报错.
而or的机制大家都知道，or前面为真直接进入了，不会判断后面了，所以不会报错后面的pop了…