首页 > 试题广场 >

有效括号序列

[编程题]有效括号序列

热度指数：372582 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给出一个仅包含字符仅由括号字符 $\texttt{`['}$ 、 $\texttt{`]'}$ 、 $\texttt{`('}$ 、 $\texttt{`)'}$ 、 $\texttt{`\{'}$ 、 $\texttt{`\}'}$ 的括号序列字符串 $s$ （ $0 \leqq |s| \leqq 10^4$ ），你需要判断给出的括号序列字符串 $s$ 是否是有效的括号序列。

$\hspace{15pt}$ 有效括号序列的定义如下：
$\hspace{23pt}\bullet\,$ 空序列是有效括号序列；
$\hspace{23pt}\bullet\,$ 如果 $A$ 是有效括号序列，则 $\texttt{(A)}$ 、 $\texttt{[A]}$ 和 $\texttt{{A}}$ 都是有效括号序列；
$\hspace{23pt}\bullet\,$ 如果 $A$ 和 $B$ 都是有效括号序列，则它们的拼接 $AB$ 也是有效括号序列。

$\hspace{15pt}$ 如果括号序列字符串 $s$ 是有效的括号序列，返回一个布尔值 $\texttt{true}$ ；否则返回一个布尔值 $\texttt{false}$ 。

示例1

输入

"["

输出

false

示例2

输入

"[]"

输出

true

备注:

要求：空间复杂度 ，时间复杂度 。

算法知识视频讲解

Python3

意若久时天然呆

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

# @param s string字符串

# @return bool布尔型

class Solution:

def isValid(self, s: str) -> bool:

# write code here

a = []

for i in s:

a.append(i) if a == [] else a.pop() if a[-1] + i in ["()", "[]", "{}"] else a.append(i)

if a == []:

return True

else:

return False

发表于 2025-11-14 18:07:22 回复(0)

Python3

牛客199588240号

class Solution:

def isValid(self , s: str) -> bool:

# write code here

print(s)

li=[]

while True:

li=s.split('[]')

s=''.join(li)

li=s.split('()')

s=''.join(li)

li=s.split(r'{}')

s=''.join(li)

if not s:

return True

elif '[]' not in s and '()' not in s and r'{}' not in s:

return False

发表于 2025-08-14 23:35:21 回复(0)

Python3

泥鳅😁

class Solution:
    def isValid(self , s: str) -> bool:
        # write code here
        stack = []
        for val in s:
            if stack == []:
                stack.append(val)
            else:
                if stack[-1] + val in ['()', '[]', '{}']:
                    stack.pop(-1)
                else:
                    stack.append(val)
        if stack == []:
            return True
        else:
            return False

定义一个空列表作为栈，遍历给定的字符串就行，当栈为空，直接将当前元素进栈。若栈不为空，就和栈顶元素进行组合匹配，如果是一个合法的括号，那就栈顶弹出。不是的就继续进栈。最后判断栈是否为空就行

发表于 2025-04-19 21:58:03 回复(1)

Python3

牛客418952426号

class Solution:

def isValid(self, s: str) -> bool:

stack = []

paren_map = {")": "(", "]": "[", "}": "{"}

for c in s:

if c not in paren_map:

stack.append(c)

elif not stack or paren_map[c] != stack.pop():

return False

return not stack

发表于 2025-01-30 10:02:23 回复(0)

Python3

孙逸凡我男神

class Solution:
    def isValid(self, s: str) -> bool:
        # 定义一个栈用于存储左括号
        stack = []
        # 定义一个字典来存储括号的匹配关系
        matching_brackets = {")": "(", "]": "[", "}": "{"}

        # 遍历字符串中的每一个字符
        for char in s:
            if char in matching_brackets.values():  # 如果是左括号，则压入栈
                stack.append(char)
            elif char in matching_brackets:  # 如果是右括号
                if not stack:  # 如果栈为空，说明没有左括号可以匹配
                    return False
                top = stack.pop()  # 弹出栈顶元素
                if top != matching_brackets[char]:  # 如果栈顶元素和当前右括号不匹配
                    return False
        # 如果栈为空，说明所有的括号都匹配，返回 True；否则返回 False
        return len(stack) == 0

发表于 2024-12-24 22:20:32 回复(0)

Python3

阿biao

class Solution:

def isValid(self , s: str) -> bool:

# write code here

stack = []

valid = {')':'(', ']':'[', '}':'{'}

for i in range(len(s)):

if s[i] in ['(', '{', '[']:

stack.append(s[i])

else:

if len(stack) == 0: return False

ele = stack.pop()

if not ele or valid[s[i]] != ele:

return False

return True if len(stack) == 0 else False

发表于 2024-12-21 17:41:38 回复(0)

Python3

ccc0212

def isValid(self , s: str):
        d_type_1 = []
        dict_1 = {'{':'}','[':']','(':')'}
        for i in s:
            if i in ['(','[','{']:
                d_type_1.append(i)
            if i in [')',']','}']:
                if len(d_type_1) != 0 and dict_1[d_type_1[-1]] == i:
                    d_type_1.pop(-1)
                else:
                    return False
        if len(d_type_1) == 0:
            return True
        else:
            return False

发表于 2024-10-31 15:15:29 回复(0)

Python3

我不上清华123

class Solution:

def isValid(self , s: str) -> bool:
    # write code here
    n = len(s)
    stack = []
    left = "({["
    right = ")}]"
    if(s and n%2 == 0 and s[0] in left):  
        for i in s:
            if(i in left):
                stack.append(i)
            else:
                if(i == ')' and stack[-1] == '('):  stack.pop()
                elif(i == '}' and stack[-1] == '{'):  stack.pop()
                elif(i == ']' and stack[-1] == '['):  stack.pop()
                else: return False
        if stack: return False
        else: return True
    else: return False

发表于 2024-09-14 01:31:35 回复(0)

Python3

九天揽月a

# 使用一个栈，左括号直接入栈，右括号判断和栈顶是否匹配，匹配则弹出栈顶，最后空栈则有效。

class Solution:
    def isValid(self, s: str) -> bool:
        # write code here
        stack = []

        left = "([{"
        right = ")]}"
        for i in s:
            if i in left:
                stack.append(i)
            elif i in right:
                if stack and stack[-1] in left and left.index(stack[-1]) == right.index(i):
                    stack.pop()
                else:
                    return False
        if not stack:
            return True
        else:
            return False

发表于 2024-08-22 10:45:57 回复(0)

Python3

小saki

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return bool布尔型
#
class Solution:
    def isValid(self, s: str) -> bool:
        # write code here
        # 辅助栈
        st = []

        for i in range(len(s)):
            if len(st) == 0:
                st.append(s[i])
            elif (
                (st[-1] == "{" and s[i] == "}")
               &nbs***bsp;(st[-1] == "[" and s[i] == "]")
               &nbs***bsp;(st[-1] == "(" and s[i] == ")")
            ):
                st.pop()
            else:
                st.append(s[i])
        return False  if len(st)!=0 else True

发表于 2024-08-05 11:13:22 回复(0)

Python3

李昂丶

class Solution:
    def isValid(self , string: str) -> bool:
        # write code here
        class Stack:
            def __init__(self):
                self.items=[]
            def isEmpty(self):
                 return self.items == []
            def push(self,item):
                self.items.append(item)
            def pop(self):
                return self.items.pop()
            def size(self):
                return len(self.items)
        def match(open,close):
            opens='([{'
            closes=')]}'
            if opens.index(open) == closes.index(close):
                return True
            else:
                return False
        s=Stack()
        balanced=True
        index=0
        while index<len(string) and balanced:
            char=string[index]
            if char in '([{':
                s.push(char)
            else:
                if s.isEmpty():
                    balanced=False  #右括号开头，无效
                else:
                    top=s.pop()
                    if not match(top,char):
                        balanced=False
            index=index+1
        if balanced and s.isEmpty():
            return True
        else:
            return False

编辑于 2024-04-16 22:00:05 回复(0)

Python3

川流不息憨憨

class Solution:
    def isValid(self , s: str) -> bool:
        stack = []
        if len(s) % 2 != 0:
            return False
        for i in s:
            # print(stack)
            if i in ("[", '{', "("):
                stack.append(i)
                continue
            elif i in ("}", ')', "]"):
                if stack == []:
                    return False
                if i == ")" and stack.pop() == "(":
                    continue
                elif i == "}" and stack.pop() == "{":
                    continue
                elif i == "]" and stack.pop() == "[":
                    continue
                else:
                    return False
            return len(stack) == 0

编辑于 2024-03-18 20:54:34 回复(0)

Python3

牛客483061681号

class Solution:
    def isValid(self , s: str) -> bool:
        # write code here
        
        if len(s) % 2 != 0:#如果长度不是偶数，直接false
            return False
        elif s[0] == ')'&nbs***bsp;s[0] == ']'&nbs***bsp;s[0] == '}':#如果第一个元素为右括号，则false
            return False
        else:#当第一个元素是左括号,判断后续元素能否一一配对
            stack = []
            for i in s:
                if i == '('&nbs***bsp;i == '['&nbs***bsp;i == '{':#所有左括号入栈
                    stack.append(i)
                else:#当遍历到右括号时
                    if i == ')' and stack[-1]!='(':#如果列表最后一位不是能与之配对的左括号，false
                        return False
                    
                    elif i == ']' and stack[-1]!='[':
                        return False
                    
                    elif i == '}' and stack[-1]!='{':
                        return False
                    else:#是能配对的，就pop
                        stack.pop()
                 
            if stack:#如果最后列表中还有元素，则false
                return False
            else:
                return True

发表于 2024-02-20 18:53:46 回复(0)

Python3

在午休的打工人很想去夏威夷

class Solution:

def isValid(self , s: str) -> bool:

# write code here

bracket_dict = {

')': '(',

']': '[',

'}':'{'

}

stack = []

for item in s:

if item in '({[':

stack.append(item)

elif len(stack)!=0 and stack[-1] == bracket_dict.get(item):

stack.pop()

else:

return False

if len(stack) == 0:

return True

return False

编辑于 2024-01-24 23:47:18 回复(0)

Python3

可道非常道

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return bool布尔型
#
class Solution:
    def isValid(self , s: str) -> bool:
        # write code here
        stack = []  # 用于存储左括号
        mapping = {')': '(', '}': '{', ']': '['}  # 定义括号对应关系
        
        for char in s:
            if char in mapping:  # 若当前字符为右括号
                if not stack&nbs***bsp;stack[-1] != mapping[char]:
                    return False  # 若栈为空或栈顶元素与当前右括号不匹配，则返回False
                stack.pop()  # 匹配成功，弹出栈顶的左括号
            else:
                stack.append(char)  # 若当前字符为左括号，压入栈中
        
        return not stack  # 若栈为空，则表示所有括号都已匹配完全，返回True，否则返回False

发表于 2023-10-18 11:09:57 回复(0)

Python3

LeoAlan

# 解法一
class Solution:
    def isValid(self, s: str) -> bool:
        # 循环替换，直到字符串为空或者不变
        while True:
            ori = s
            s = s.replace("()", "").replace("{}", "").replace("[]", "")
            # 如果字符串为空，则为True
            if not s:
                return True
            # 如果字符串不再发生变化，则为False
            if s == ori:
                return False


# 解法二
class Solution:
    def isValid(self, s: str) -> bool:
        # 定义一个映射关系
        def judge_duichen(s1, s2):
            mapping = {"}": "{", ")": "(", "]": "["}
            return True if s2 in mapping and mapping[s2] == s1 else False

        # 定义一个列表，用来存储当前入栈的元素
        all = []
        for i in s:
            # 如果当前栈为空，则将当前元素入栈，并且跳到下一次循环
            if not all:
                all = [i]
                continue
            # 如果当前元素与栈顶元素对称，则将栈顶元素出栈
            if judge_duichen(all[-1], i):
                all.pop()
            # 如果不对称，则将当前元素入栈
            else:
                all.append(i)
        # 如果栈为空，则为True，否则为False
        return all == []


# 解法三：
class Solution:
    def isValid(self, s: str) -> bool:
        all = []
        mapping = {"}": "{", ")": "(", "]": "["}
        # 先让所有的左括号入栈
        for i in s:
            if i in "{[(":
                all.append(i)
            # 如果当前元素是右括号，且栈为空，则返回False，因为右括号不能先于左括号出现
            elif all == []:
                return False
            # 如果当前元素是右括号，则判断栈顶元素是否与其对称，如果对称，则将栈顶元素出栈，否则返回False
            elif mapping[i] == all[-1]:
                all.pop()
            else:
                return False
        # 在循环结束后，如果栈为空，则为True，否则为False
        return all == []

发表于 2023-09-17 11:48:44 回复(0)

Python3

zackw

class Solution:
    def isValid(self , s: str) -> bool:
        # write code here
        if len(s)%2 == 1:
            return False
        else:
            stack = []  # 左括号入栈，右括号没必要入栈，入了后续也不可能匹配上
            pairs = ["()","[]","{}"]
            for i in range(len(s)):
                if s[i] in "({[":
                    stack.append(s[i])
                else:   #输入的是右括号
                    if len(stack) == 0:
                        return False    # 栈里没有左括号和右括号匹配
                    else:
                        pair = stack[-1]+s[i]
                        if pair in pairs:
                            stack.pop(-1)   # 匹配成功则弹出栈里的最后一个左括号
                        else:
                            return False # 如果栈里最后一个左括号和右括号不匹配则永远不会匹配上了
            if len(stack) == 0: # 判断所有左括号是否全部出栈
                return True
            else:
                return False

发表于 2023-09-12 20:09:47 回复(0)

Python3

不刷题怎么进大厂

请问为什么我的代码会提示列表越界？

class Solution:

def isValid(self , s: str) -> bool:

# write code here

n = len(s)

if n%2 != 0:

return False

ls = []

for a in range(n):

while a<n and (s[a] == '(' or s[a] == '[' or s[a] == '{'):

ls.append(s[a])

a += 1

if s[a] == ')' and ls[-1] == '(':

ls.pop()

elif s[a] == ']' and ls[-1] == '[':

ls.pop()

elif s[a] == '}' and ls[-1] == '{':

ls.pop()

if not ls:

return True

else :

return False

发表于 2023-07-05 00:16:56 回复(1)

提交观点

问题信息

字符串栈

难度：

27条回答 1378收藏 39815浏览

通过挑战的用户

查看代码

牛客65488...

2023-01-31 19:12:46
牛客67688...

2022-12-07 13:58:39
信达雅

2022-11-26 13:12:57
兜小弟

2022-11-13 10:57:05
曾罗

2022-10-28 16:11:48

有效括号序列

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题