首页 > 试题广场 >

有效括号序列

[编程题]有效括号序列
  • 热度指数:307434 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给出一个仅包含字符'(',')','{','}','['和']',的字符串,判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭,"()"和"()[]{}"都是合法的括号序列,但"(]""([)]"不合法

数据范围:字符串长度
要求:空间复杂度 ,时间复杂度
示例1

输入

"["

输出

false
示例2

输入

"[]"

输出

true
import java.util.*;
//用一个hashmap保存括号对,代码更简洁
public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
        for(int i = 0; i < s.length(); i++) {
            if(stack.isEmpty()) {
                stack.push(s.charAt(i));
                continue;
            } 
             if(stack.peek().equals(map.get(s.charAt(i) ) ) ) {
                 stack.pop();
             } else {
              stack.push(s.charAt(i));
             }
        }
        return stack.isEmpty();
    }
}
发表于 2017-06-21 13:02:59 回复(0)
    bool isValid(string s) {
        // write code here
        if (s.size() <= 1)
        {
            return false;
        }
        stack<char> temp;
        for(int i = 0; i<s.size();i++)
        {
            if(temp.size() == 0)
            {
                temp.push(s[i]);
            }
            else
            {
                char ch = temp.top();
                if((ch == '(' && s[i] == ')') || (ch == '[' && s[i] == ']') ||
                   (ch == '{' && s[i] == '}'))
                {
                    temp.pop();
                }
                else
                {
                    temp.push(s[i]);
                }
            }
        }
        return temp.size() == 0 ? 1 :0;
    }
};

发表于 2020-11-03 22:45:04 回复(0)
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 回复(8)
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)
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)
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)
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)
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)
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)
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)
这题可以和编译原理的课程内容联系起来,这类的界符合法性校验,首先可以用一个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)
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)
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 回复(1)
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)
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)
    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)
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)
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)
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)
public boolean isValid (String s) {
        // write code here
        //利用哈希存储字符,避免if语句中出现冗余比较语句
        HashMap<Character, Character> map = new HashMap<Character, Character>() {
            {
                put(')', '(');
                put(']', '[');
                put('}', '{');
            }
        };
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                if (stack.isEmpty()) return false;
                if (map.get(c) != stack.peek()) return false;
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }

发表于 2023-03-20 20:13:26 回复(1)