首页 > 试题广场 >

有效括号序列

[编程题]有效括号序列

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

备注:

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

算法知识视频讲解

Java

fixxx

JAVA

自己写了个栈，不想再包装获取top的方法了，就直接使用了。。。判断的逻辑也比较啰嗦，但是能跑。

java

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        int length = s.length();
        if(length%2==1){
            return false;
        }
        MyStack stack = new MyStack(length);
        for (int i = 0; i < length; i++) {
            char element = s.charAt(i);
            if (element == '[' || element == '(' || element == '{') {
                stack.push(element);
            } else {
                if (stack.top == -1) {
                    return false;
                } else {
                    char topElement = stack.pull();
                    if ((topElement == '[' && element == ']') || (topElement == '(' &&
                            element == ')') || (topElement == '{' && element == '}')) {
                        continue;
                    }else {
                        return false;
                    }
                }
            }
        }
        return stack.top==-1;
    }



    class MyStack {
        int top ;
        private char[] stack;

        public MyStack(int length) {
            stack = new char[length];
            top = -1;
        }

        public void push(char element) {
            stack[++top] = element;
        }

        public char pull() {
            if (top != -1) {
                return stack[top--] ;
            }
            return 'x';
        }
        public char peek() {
            if (top != -1) {
                return stack[top];
            }
            return 'x';
        }
    }
}

发表于 2025-08-08 21:44:16 回复(0)

Java

拒绝无效加班的柯基很想被叫靓仔

public class Solution {

/**

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

* @param s string字符串

* @return bool布尔型

public boolean isValid (String s) {

// write code here

Deque<Character> stack = new ArrayDeque<>();

for(char c:s.toCharArray()){

if(c == '(' || c == '[' || c == '{'){//如果输入括号左边直接入栈

stack.push(c);

}else{

if(c == ')'){//如果输入括号右边，判断栈顶元素能否闭合，若空栈则入栈并终止循环；若非空栈且能闭合则取出栈顶元素

if(stack.isEmpty()){return false;}

else if(!stack.isEmpty() && stack.peek() =='('){stack.pop();}

}else if(c == ']'){

if(stack.isEmpty()){return false;}

else if(!stack.isEmpty() && stack.peek() =='['){stack.pop();}

}else if(c == '}'){

if(stack.isEmpty()){return false;}

else if(!stack.isEmpty() && stack.peek() =='{'){stack.pop();}

}

return stack.isEmpty()?true:false;

}

发表于 2025-07-11 00:05:43 回复(0)

Java

有力量的小白要双休

import java.util.*;

public class Solution {

    public boolean isValid (String s) {
        // 使用栈来跟踪最近的开括号
        Stack<Character> stack = new Stack<>();

        // 遍历字符串中的每个字符
        for (char c : s.toCharArray()) {
            // 如果是开括号，压入栈中
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                // 如果是闭括号，检查栈是否为空或栈顶元素是否匹配
                if (stack.isEmpty() || !isMatchingPair(stack.peek(), c)) {
                    return false;
                }
                // 如果匹配，弹出栈顶元素
                stack.pop();
            }
        }

        // 如果栈为空，则所有括号都正确匹配
        return stack.isEmpty();
    }

    // 检查两个字符是否是匹配的括号对
    private static boolean isMatchingPair(char open, char close) {
        return (open == '(' && close == ')') ||
               (open == '[' && close == ']') ||
               (open == '{' && close == '}');
    }
}

发表于 2024-10-19 12:32:36 回复(0)

Java

HarryLai

public class Solution {
    private Character pair(Character c) {
        switch(c) {
            case ')': return '(';
            case ']': return '[';
            case '}': return '{';
            default: return null;
        }
    }
    
    public boolean isValid (String s) {
        Stack<Character> stack = new Stack<>();
        Character c;
        for (int i=0; i<s.length(); i++) {
            c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (!stack.empty() && pair(c) == stack.peek()) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if (!stack.empty()) {
            return false;
        }
        return true;
    }
}

发表于 2024-10-19 11:27:48 回复(0)

Java

渔鱼123

public class Solution {
    public boolean isValid (String s) {
        if (s.length() % 2 != 0) return false;
        char[] arr = s.toCharArray();
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '(' || arr[i] == '[' || arr[i] == '{') {
                stack.push(arr[i]);
            } else if (!stack.isEmpty()) {
                if (arr[i] == ')') {
                    if (stack.peek() == '(') stack.pop();
                    else return false;
                } else if (arr[i] == ']') {
                    if (stack.peek() == '[') stack.pop();
                    else return false;
                } else if (arr[i] == '}') {
                    if (stack.peek() == '{') stack.pop();
                    else return false;
                } else return false;
            }
        }
        return stack.isEmpty();
    }
}

发表于 2024-10-14 23:25:45 回复(0)

Java

人间水长东

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here

        // 1.创建一个栈，用来匹配左右括号
        Stack<Character> stack = new Stack<>();

        // 2.遍历字符串
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                // 如果是左括号，直接入栈
                stack.push(c);
            } else if (c == ')') {
                // 如果是')'，则观察栈顶元素，若是'('则出栈
                if (!stack.isEmpty() && stack.peek() == '(') {
                    stack.pop();
                } else {
                    return false;
                }
            } else if (c == '}') {
                // 如果是'}'，则观察栈顶元素，若是'{'则出栈
                if (!stack.isEmpty() && stack.peek() == '{') {
                    stack.pop();
                } else {
                    return false;
                }
            } else if (c == ']') {
                // 如果是']'，则观察栈顶元素，若是'['则出栈
                if (!stack.isEmpty() && stack.peek() == '[') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }

        // 3.若栈空，则有效
        return stack.isEmpty();
    }
}

发表于 2024-08-07 20:47:54 回复(0)

Java

你好，侦探先生

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here

        String[] split = s.split(",");
        int length = split.length;
        if (length == 1 ) {
            return false;
        } else {
            if (length % 2 != 0) {
                return false;
            } else {
                boolean flag  = true;
                int i = 0;

                while (flag) {
                    if (split[i] == "(") {
                        if (split[i + 1] == ")") {
                            flag =  true;
                        } else flag = false;
                    } else if (split[i] == "[") {
                        if (split[i + 1] == "]") {
                            flag = true;
                        } else flag = false;
                    } else if (split[i] == "{") {
                        if (split[i + 1] == "}") {
                            flag = true;
                        } else flag = false;
                    } else flag = false;
                }
                return flag;
            }
        }
    }
}

编辑于 2024-03-26 16:20:34 回复(0)

Java

兔子与胡萝卜

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        Deque<Character> deque = new ArrayDeque<Character>();
        // s = s.substring(1, s.length() - 1);
        System.out.println(s);
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                deque.push(c);
            } else {
                if (deque.size() == 0) {
                    return false;
                }
                char c1 = deque.pop();
                String str = c1 + "" + c;
                if (!(str.equals("()") || str.equals("[]") || str.equals("{}"))) {
                    return false;
                }
            }
        }
        return deque.size() == 0 ? true : false;
    }
}

编辑于 2023-12-08 00:25:20 回复(1)

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

dqxfz

public boolean isValid (String s) {

Stack<Character> stack = new Stack<>();

for (int i = 0; i < s.length(); i++) {

char ch = s.charAt(i);

if (stack.isEmpty()) {

stack.push(ch);

} else {

char top = stack.peek();

if ((top == '(' && ch == ')') || (top == '{' && ch == '}') || (top == '[' &&

ch == ']')) {

stack.pop();

} else {

stack.push(ch);

}

return stack.isEmpty();

}

发表于 2023-09-23 19:59:07 回复(0)

Java

牛客781396821号

本来是准备暴力解决的，但是突然看到有人使用栈，想到这个题明显和栈很搭，所以重新用栈写了一遍回答

import java.util.*;


public class Solution {
    class AAAA {
        char c;
        AAAA next;
        AAAA pri;

        public AAAA (char c) {
            this.c = c;
        }
    }
    AAAA quene;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        int lenght = s.length();
        quene = new AAAA('0');
        for (int i = 0; i < lenght ; i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                // 入栈
                addAAAA(c);
                // 出栈并检查
            } else if (quene.c == '0' || !check(c)) {
                return false;
            }
        }
        return quene.c == '0';
    }

    public boolean check (char c) {
        // ')' - '(' == 1;
        // ']' - '[' == 2;
        // '}' - '{' == 2
        char a = outAAAA();
        return (c - a < 3) && (c - a > 0);
    }

    public boolean addAAAA (char c) {
        AAAA q = new AAAA(c);
        q.pri = quene;
        quene.next = q;
        quene = q;
        return true;
    }

    // 出栈
    public char outAAAA() {
        char c = quene.c;
        AAAA q = quene.pri;
        quene.pri = null;
        quene = q;
        quene.next = null;
        return c;
    }
}

发表于 2023-08-19 17:14:56 回复(0)

Java

DDwu

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        Stack<Character> s1 = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '{' || s.charAt(i) == '[' || s.charAt(i) == '(') {
                s1.push(s.charAt(i));
            } else {
                if (!s1.isEmpty() && isMatch(s1.peek(), s.charAt(i))) {
                    s1.pop();
                } else {
                    return false;
                }
            }
        }
        if (s1.isEmpty()) return true;
        return false;
    }
    public boolean isMatch (char s1, char s2) {

        switch (s1) {
            case '{':
                return '}' == s2 ? true : false;
            case '[':
                return ']' == s2 ? true : false;
            case '(':
                return ')' == s2 ? true : false;
        }
        return false;
    }
}

发表于 2023-08-12 16:27:07 回复(0)

Java

牛客533503588号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        if (s.length() == 0 || s.length() % 2 == 1) {
            return false;
        }
        if (s.charAt(0) == ')' || s.charAt(0) == '}' || s.charAt(0) == ']') {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
                stack.push(s.charAt(i));
            } else {
                Character pop = stack.pop();
                if (s.charAt(i) == ')' && pop != '(') {
                    return false;
                }
                if (s.charAt(i) == '}' && pop != '{') {
                    return false;
                }
                if (s.charAt(i) == ']' && pop != '[') {
                    return false;
                }
            }
        }
        return stack.size() == 0;
    }
}

发表于 2023-08-11 23:01:28 回复(0)

Java

延时追逐

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public static boolean isValid (String s) {
        // write code here
        if ((s.length() % 2) != 0) {
            return false;
        }
        int i = 0;
        StringBuilder sb = new StringBuilder(s);
        while (s.length() >= 2) {
            if ((s.charAt(i) == '(') && (s.charAt(i + 1) == ')')) {
                sb.delete(i, i + 2);
                s = sb.toString();
                i = 0;
                continue;
            }
            if ((s.charAt(i) == '[') && (s.charAt(i + 1) == ']')) {
                sb.delete(i, i + 2);
                s = sb.toString();
                i = 0;
                continue;
            }
            if ((s.charAt(i) == '{') && (s.charAt(i + 1) == '}')) {
                sb.delete(i, i + 2);
                s = sb.toString();
                i = 0;
                continue;
            }
            i++;
            if (i == s.length() - 1) {
                return false;
            }
        }
        return true;
    }
}

发表于 2023-08-05 17:29:47 回复(0)

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)

Java

抓住努力的尾巴

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        if(s == null || s.length() == 0) {
            return true;
        }
        int len = s.length();
        if(len % 2 != 0) {
            return false;
        }

        char[] chs = s.toCharArray();
        Stack<Character> sta = new Stack<>();
        for(int i = 0; i < chs.length; i++) {
            if(chs[i] == '(' || chs[i] == '{' || chs[i] == '[') {
                sta.push(chs[i]); 
            } else if(sta.isEmpty()) {
                return false;
            } else {
                char ch = sta.peek();
                if(ch == '(' && chs[i] == ')') {
                    sta.pop();
                } else if(ch == '{' && chs[i] == '}') {
                    sta.pop();
                } else if(ch == '[' && chs[i] == ']') {
                    sta.pop();
                } else {
                    return false;
                }
            }
        }
        return sta.isEmpty();
    }
}

发表于 2023-07-15 16:13:38 回复(0)

Java

勤奋的nana

import java.util.*;

public class Solution {

/**

* @param s string字符串

* @return bool布尔型

public boolean isValid (String s) {

// write code here

String[] str=s.split("");

int flag=0;

for(int i=0;i<str.length/2;i++){

if((str[i].equals("(")&&str[str.length-i-1].equals(")")) || (str[i].equals("[")&&str[str.length-i-1].equals("]")

)|| (str[i].equals("{")&&str[str.length-i-1].equals("}"))){

flag=1;

}

else {

flag=0;

}

if(flag==1) return true;

return false;

}

发表于 2023-06-14 17:34:08 回复(0)

Java

老菜鸟养乐多

使用stack，解决问题很容易

import java.util.*;


public class Solution {
    /**
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!stack.isEmpty()) {
                if (c == ')' && stack.pop() == '(') {
                    continue;
                }
                if (c == ']' &&  stack.pop() == '[') {
                    continue;
                }
                if (c == '}' && stack.pop() == '{') {
                    continue;
                }
            }
            stack.add(c);
        }
        return stack.isEmpty();
    }
}

发表于 2023-05-16 22:47:21 回复(2)

提交观点

问题信息

字符串栈

难度：

109条回答 1378收藏 39897浏览

通过挑战的用户

查看代码

牛客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

有效括号序列

输入

输出

输入

输出

备注:

JAVA

自己写了个栈，不想再包装获取top的方法了，就直接使用了。。。判断的逻辑也比较啰嗦，但是能跑。

问题信息

热门推荐

通过挑战的用户

相关试题

有效括号序列

输入

输出

输入

输出

备注:

JAVA

自己写了个栈，不想再包装获取top的方法了，就直接使用了。。。 判断的逻辑也比较啰嗦，但是能跑。

问题信息

热门推荐

通过挑战的用户

相关试题

自己写了个栈，不想再包装获取top的方法了，就直接使用了。。。判断的逻辑也比较啰嗦，但是能跑。