栈与队列-有效的括号匹配

Posted on

栈的运用中经典中的经典 不过算法竞赛不会考这些导致当时就没用心去搞懂
题干：
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。

不匹配的情况只有三种 搞懂就是很简单的题目！！

不匹配的三种情况如下

  • 左边拥有冗余括号 例如 ((({[]})

  • 中部拥有匹配错误的情况 例如 ({[)})

  • 右部拥有冗余括号 例如 ({[]})))))

编写的逻辑也很简单
遍历字符串 当遇到左括号时 将匹配的右括号压入栈中; 当遇到右括号时,弹出栈顶元素观察是否是同一种类的右括号;
如果中途出现不同 则是情况二
如果遍历完字符串 栈内还有元素 则是情况一
如果遍历字符串中途 栈中已经没有元素了 则是情况三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
       	stk=[]   # python没有专门的栈结构  但是list可以完美实现栈的基本功能
        for item in s:
            if item =='(':
                stk.append(')')
            elif item == '{':
                stk.append('}')
            elif item == '[':
                stk.append(']')
            elif not stk or item !=stk[-1]:
                return False
            else :
                stk.pop()
        return True if not stk else False