首页 > 试题广场 >

有效括号序列

[编程题]有效括号序列

热度指数：371165 时间限制：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

备注:

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

算法知识视频讲解

查看答案及解析

JacobGo！

import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
		Stack<Character> stack = new Stack<Character>();
		//使用foreach循环
		for (char c : s.toCharArray()) {
			if (c == '(')
				stack.push(')');
			else if (c == '{')
				stack.push('}');
			else if (c == '[')
				stack.push(']');
			else if (stack.isEmpty() || stack.pop() != c)
				return false;
		}
		return stack.isEmpty();
	}
}

编辑于 2017-07-19 10:33:18 回复(9)

潘多拉Boot

class Solution {
public:
    bool isValid(string s) {
        int len=s.size();
        stack<char> sta;
        for(int i=0;i<len;i++){
            if(s[i]=='(')sta.push(')');
            else if(s[i]=='[')sta.push(']');
            else if(s[i]=='{')sta.push('}');
            else if(sta.empty())return false;
            else if(sta.top()!=s[i])return false;
            else sta.pop();
        }
        return sta.empty();
    }
};

发表于 2018-05-20 14:50:09 回复(0)

C/C++

nbgao

class Solution {
public:
    bool isValid(string s) {
        int l = s.length();
        stack<char> st;
        for(int i=0;i<l;i++)
        {
        	if(s[i] == '(')
        		st.push(')');
        	else if(s[i] == '[')
        		st.push(']');
        	else if(s[i] == '{')
        		st.push('}');
        	else if(st.empty())
        		return false;
        	else if(st.top() != s[i])
        		return false;
        	else
        		st.pop();
		}
		return st.empty();
    }
};

发表于 2017-08-24 01:15:52 回复(0)

Python3

悠悠小水草

class Solution:
    def isValid(self , s ):
        d = {'}': '{', ']': '[', ')': '('}
        stack = []
        for char in s:
            if char in '{[(':
                stack.append(char)
            if char in '}])':
                if not stack:
                    return False
                else:
                    if d[char] == stack[-1]:
                        stack.pop()
                    else:
                        return False
        return not stack

发表于 2021-09-05 23:35:22 回复(0)

shijiacheng

import java.util.Stack;

/**
 * 20. Valid ParentTheses
 * 有效的括号
 * <p>
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 * 示例 1:
 * 输入: "()"
 * 输出: true
 * 示例 2:
 * 输入: "()[]{}"
 * 输出: true
 * 示例 3:
 * 输入: "(]"
 * 输出: false
 * 示例 4:
 * 输入: "([)]"
 * 输出: false
 * 示例 5:
 * 输入: "{[]}"
 * 输出: true
 */
public class Solution {
    /**
     * 用压栈弹栈的方式来实现
     */
    public boolean isValid(String s) {
        if (s == null || s.length() == 0){
            return true;
        }
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '('){
                stack.push(')');
            }
            else if (chars[i] == '['){
                stack.push(']');
            }
            else if (chars[i] == '{'){
                stack.push('}');
            }
            else if (stack.isEmpty() || chars[i] != stack.pop()){
                return false;
            }
        }
        return stack.isEmpty();

    }

    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.isValid(""));
        System.out.println(solution.isValid("()[]{}"));
        System.out.println(solution.isValid("(]"));
        System.out.println(solution.isValid("([)]"));
        System.out.println(solution.isValid("{[]}"));
    }
}

发表于 2018-08-08 23:22:35 回复(0)

无心2019

class Solution {
public:
    bool isValid(string s) {
        stack<char>st;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='('||s[i]=='['||s[i]=='{')
                st.push(s[i]);
            else
            {
                if(st.empty())
                    return false;
                else
                {
                    if(s[i]==')'&&st.top()=='(')
                        st.pop();
                    else if(s[i]==']'&&st.top()=='[')
                        st.pop();
                    else if(s[i]=='}'&&st.top()=='{')
                        st.pop();
                }
            }
        }
        if(st.empty())
            return true;
        else 
            return false;
    }
};

发表于 2019-05-18 22:18:35 回复(0)

大灰兔

class Solution(object):
    def isValid(self, s):
        stack = []
        for ss in s:
            if ss == "(" or ss == "{" or ss == "[":
                stack.append(ss)
            elif ss == ")":
                if len(stack) == 0 or stack.pop() != "(":
                    return False
            elif ss == "}":
                if len(stack) == 0 or stack.pop() != "{":
                    return False
            elif ss == "]":
                if len(stack) == 0 or stack.pop() != "[":
                    return False
        return len(stack) == 0

发表于 2017-10-08 01:03:30 回复(0)

C++

Ranly

这题可以和编译原理的课程内容联系起来，这类的界符合法性校验，首先可以用一个hashmap表示界符的映射关系，免去写if else判断，其次需要利用一个栈来逐个输入符号。当输入符号ch是栈顶符号的后继时（即，讲栈顶符号输入映射表查询到的符号和输入的相同），表明栈顶和输入符号构成一对界符，因此将栈顶弹出。否则将输入符号压入栈。当字符串的所有字符都被扫描一遍后，若栈不为空，则说明界符不合法，否则合法。

class Solution {
    unordered_map<char, char> map = {{'{', '}'}, {'[', ']'}, {'(', ')'}};
  public:
    /**
     *
     * @param s string字符串
     * @return bool布尔型
     */
    bool isValid(string s) {
        stack<char> st;
        for (char& ch : s) {
            if (st.empty() || map[st.top()] != ch) {
                st.push(ch);
            } else {
                st.pop();
            }
        }
        return st.empty();
    }
};

发表于 2023-03-28 17:16:50 回复(0)

Java

huangziqiang

public boolean isValid (String s) {
        // write code here
        //遇到括号匹配这样的题，首选使用栈来做
        //每次遍历遇到'('、'['和'{'时，就将其对应的方括号')'、']'和'}'放入栈中
        //然后遍历下一个，并与栈顶元素进行比较
        //如果不同直接返回false；如果相同就将栈顶的反括号弹出，遍历结束都没有返回false就说明合法，返回true
        Stack<Character> stack = new Stack<>();
        char[] temp = s.toCharArray();
        for (char c : temp){//遍历字符，如果遇到左括号，就把相应的右括号压入栈顶
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            //else if (stack.isEmpty()) return false;//字符还没有遍历完就出现栈为空就返回false
            //else if (stack.pop() != c) return false;//如果能到达这一步，就每次从栈顶pop出一个元素与当前元素c
                                                    //进行比较，如果不同就返回false
            //也可以将上面两行代码合并：
            else if (stack.isEmpty() || stack.pop() != c) return false;
        }
        return stack.isEmpty();//遍历结束如果栈为空就返回true，否则返回false
    }

发表于 2021-08-18 13:59:43 回复(5)

JavaScript Node

rick_Han

function isValid(s) {
    // write code here
    let len = s.length
    for (let i = 0; i < len / 2; i++){
        s = s.replace("{}", "").replace("()", "").replace("[]", "");
        console.log(s)
    }
    
    return s === ''
}

发表于 2023-04-11 09:18:34 回复(2)

Java

远吗？

import java.util.*;


public class Solution {
    /**
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        // write code here
        int length = s.length();
        if (length % 2 != 0) {
            return false;
        }
        String s1 = s;
        for (int i = 0; i < length / 2; i++) {
            s1 = s1.replace("()", "").replace("[]", "").replace("{}", "");
        }
        return s1.length() <= 0;
    }
}

我偷鸡了😂

发表于 2022-11-30 08:36:49 回复(1)

Python3

Joy_9

class Solution:
    def isValid(self , s: str) -> bool:
        dic={"}":"{",")":"(","]":"["}
        half=[]
        for v in s:
            if v in '{([':
                half.append(v)
            elif v in ']})':
                if len(half)>0 and dic[v]==half[-1]:
                    half.pop()
                else:
                    return False
        return len(half)==0

发表于 2021-12-28 03:37:38 回复(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)

帅奶哟。

int i = 0, j = -1;
char a[10000];

bool isValid(char* s ) {
    // write code here
    while (s[i] != '\0') {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {    //左括号进栈
            a[++j] = s[i];
        }
        else {          //是右括号则判断是否匹配
            if (s[i] == ')' && a[j] != '(') return false;
            else if (s[i] == ']' && a[j] != '[') return false;
            else if (s[i] == '}' && a[j] != '{') return false;
            else j--;
        }
        i++;    //指向字符串下一个字符
    }
    if (j >= 0) return false;   //栈非空
    else return true;
}

发表于 2023-03-17 15:16:39 回复(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)

Java

牛客839384289号

    public boolean isValid (String s) {
        // write code here
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(c=='['){
                stack.push(']');
            }else if(c=='{'){
                stack.push('}');
            }else if(c=='('){
                stack.push(')');
            }else if(stack.isEmpty() || stack.pop()!=c){
                return false;
            }
        }
        return stack.isEmpty();
    }

发表于 2022-06-25 15:11:27 回复(1)

JavaScript Node

FoRtCurious

function isValid( s ) {
    // write code here
    if (s.length === 0 || s.length %2 === 1) return false;

    let reg = /|\[\]|\{\}/g
    while (s.match(reg)) {
        s = s.replace(reg, '')
    }
    return s.length === 0

}

发表于 2021-12-11 16:29:13 回复(0)

c++好难

class Solution {
public:
    bool isValid(string s) {
        stack<char>S;
        for(int i=0;i<s.length();++i){
            if(s[i]=='[' || s[i]=='(' || s[i]=='{') S.push(s[i]);
            else if(S.empty()) return false;
            else if(s[i]==']' && S.top()=='[' || s[i]=='}' && S.top()=='{' || s[i]==')' && S.top()=='(') S.pop();
            else return false;
        }
        if(S.empty()) return true;
        else return false;
    }
};

发表于 2018-06-22 21:46:15 回复(0)

Java

王威翰

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

        Stack<Character> signs = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (signs.empty() || map.values().contains(s.charAt(i))) { // open sign
                signs.push(s.charAt(i));
            } else { // close sign
                if (signs.peek() == map.get(s.charAt(i))) {
                    signs.pop();
                }
            }
        }

        return signs.empty() ? true : false;
    }
}

发表于 2023-11-19 17:54:18 回复(1)

Java

做则必成的勇气和信心

public boolean isValid (String s) {
        Stack<Character> st=new Stack<>();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                st.push(')');
            }else if(s.charAt(i)=='['){
                st.push(']');
            }else if(s.charAt(i)=='{'){
                st.push('}');
            }else{  //不是增加元素，是要弹出，但st为空，那就false
                if(st.isEmpty()){
                    return false;
                }
                if(st.pop()!=s.charAt(i)){
                    return false;
                }
            }
        }
        if(!st.isEmpty()){
            return false;
        }
        return true;
    }

发表于 2023-07-19 10:58:36 回复(0)