有效的括号020 -力扣（栈+py3）

阳光穿透心脏的1/2处 2022-12-23 00:45 18阅读 0赞

# 题目描述： #

给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”  
输出: true  
示例 2:

输入: “()\[\]\{\}”  
输出: true  
示例 3:

输入: “(\]”  
输出: false  
示例 4:

输入: “(\[)\]”  
输出: false  
示例 5:

输入: “\{\[\]\}”  
输出: true

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/valid-parentheses

# 解法 #

看到这个题目很自然的想到使用栈去进行解决，我个人认为一定要把代码写的优雅一点，前面两份代码是自己写的，第三份是参考的别人的，下面的三份代码都是可以通过的，可以对比一下，看看怎么去把代码变得优雅一些。

首先说一下解题思路：  
初始化栈，python中最简单的栈就是list，依次读取字符串中的字符  
栈判空，若空则入栈  
对于读取到’(’，’\{’，’\{'进行入栈操作  
若读取到右括号，则与栈顶元素匹配，若匹配则出栈，否则无效  
最后判断栈是否为空，为空则有效，否则无效

整体思路是这样的，下面是具体实现，下面的实现和上面的大思路是一致的，不过具体实现的方式略有不同：

第一种方式：

def isValid(self, s: str) -> bool:
            stack = []
            for char in s:
                if len(stack) == 0:
                    stack.append(char)
                else:
                    if char == ')' and stack[-1] == '(' or char == ']' and stack[-1] == '[' or char == '}' \
                            and stack[-1] == '{':
                        stack.pop()
                    else:
                        stack.append(char)
            if len(stack) != 0:
                return False
    
            return True
    # 例如，此处最后的三行代码就可以直接转换为return not stack，这些地方可以改进，代码这样看起来更加整洁

第二种方式

stack = []
            dic = { '(': ')', '[': ']', '{': '}'}
            for char in s:
                if not stack:
                    stack.append(char)
                else:
                    flag = False
                    for key, value in dic.items():
                        if char == value and stack[-1] == key:
                            flag = True
                            break
                    if flag:
                        stack.pop()
                    else:
                        stack.append(char)
    
            return not stack

第三种方式  
最初写的

stack = []
            dic = { '(': ')', '[': ']', '{': '}'}
            for char in s:
                if not stack:
                    if char not in dic:
                        return False
                    stack.append(char)
                elif char in dic:
                    stack.append(char)
                elif dic[stack[-1]] != char:
                    return False
                else:
                    stack.pop()
            return not stack

进一步改进，对于list的pop函数，返回值为其本身的值，这个地方应用该特点将其作为key去寻找value，同时也进行了pop操作。

dic = { '{': '}', '[': ']', '(': ')'}
            stack = []
            for char in s:
                if not stack:
                    if char not in dic:
                        return False
                    stack.append(char)
                elif char in dic:
                    stack.append(char)
                elif dic[stack.pop()] != char:
                    return False
            return not stack

别人的，人家直接新建了一个键值对，保证pop操作不会出错

def isValid(self, s: str) -> bool:
            dic = { '{': '}',  '[': ']', '(': ')', '?': '?'}
            stack = ['?']
            for c in s:
                if c in dic: stack.append(c)
                elif dic[stack.pop()] != c: return False 
            return len(stack) == 1
    # 这个地方人家处理的太巧了，膜拜大佬

第三种方式的代码链接：https://leetcode-cn.com/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/