[编程题]括号序列

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

给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

示例1

输入

"["

输出

false

示例2

输入

"[]"

输出

true

算法知识视频讲解

潘多拉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)

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 回复(7)

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)

食肉大灰兔

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/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)

无心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)

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)

风中追风20180314092925

关键建立一个反映射，这里用的map，入栈时入对应括号出栈再判断也可以

bool isValid(string s) {
    int n = s.size();
    if(n < 1) return true;
    
    stack<char> sk;
    map<char, char> mp = {{')','('}, {']','['}, {'}','{'}};
    
    for(int i = 0; i < n; ++i){
        if(s[i] == '(' || s[i] == '[' || s[i] == '{')
            sk.push(s[i]);
        else if(!sk.empty() && mp[s[i]] == sk.top()){
            sk.pop();
        }
        else{
            return false;
        }
    }
    if(!sk.empty())
        return false;
    
    return true;
}

发表于 2019-05-07 21:36:44 回复(0)

RmondJone

        if(s.length()%2!=0){
           return false; 
        }
        Stack<Character> stack=new Stack();
        for(int i=0;i<s.length();i++){
          if(stack.isEmpty()){
             stack.push(s.charAt(i));
             continue; 
          } 
          if(stack.peek()=='(' && s.charAt(i)==')'){
             stack.pop(); 
          }else if(stack.peek()=='{' && s.charAt(i)=='}'){
             stack.pop(); 
          }else if(stack.peek()=='[' && s.charAt(i)==']'){
             stack.pop(); 
          }else{
             stack.push(s.charAt(i)); 
          }   
        }
        return stack.isEmpty();

发表于 2021-01-21 10:51:34 回复(0)

Haifly

    bool isValid(string s) { //map +stack
        map<char, char> valume = {{'(',')'}, {'{', '}'}, {'[', ']'}};
        stack<char> test;
        for (int i = 0;i < s.size(); i++) {
             char top = '-';
            if (!test.empty()) top = test.top();
            if (valume[top] == s[i]) {
                test.pop();
                continue;
            } 
            test.push(s[i]);
        }
        return test.empty();
    }

编辑于 2020-11-05 23:19:08 回复(0)

Mr-13th

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool isValid(string s) {
        // write code here
        stack<char> st;
        int length = s.size();
        for(int i=0;i<length;i++){
            if(s[i]=='(') st.push(')');
            else if(s[i]=='[') st.push(']');
            else if(s[i]=='{') st.push('}');
            else {
                if(st.empty()) return false;
                char temp = st.top();
                st.pop();
                if(temp!=s[i]) return false;
            }
        }
        return st.empty();
};
};

发表于 2020-08-02 18:13:58 回复(0)

C/C++

华科平凡

c++ solution:

class Solution {
public:
    bool isValid(string s) {
        stack<char> stack1;
        for (char c:s) {
            if (c == '(' || c == '{' || c == '[') {
                stack1.push(c);
            } else if (stack1.empty())
                return false;
            else if ((c == '}' && stack1.top() == '{') ||
                     (c == ']' && stack1.top() == '[') ||
                     (c == ')' && stack1.top() == '('))
                stack1.pop();
            else
                return false;
        }
        return stack1.empty();
    }
};

发表于 2018-09-17 16:03:31 回复(0)

ID84848484

感觉有点笨。。。

class Solution {
public:
    bool isValid(string s) {
        int n=s.length();
        if(n%2==1)
            return false;
        if(n==0)
            return true;
        stack<char> sta;
        sta.push(s[0]);
        int i=1;
        if(s[0]==')' || s[0]=='}' || s[0]=='}')
            return false;
        while(!sta.empty() && i<n){
            char ch=sta.top();
            if(ch=='(' && s[i]!=')')
            {
                sta.push(s[i]);
                i++;
                continue;
            }
            if(ch=='[' && s[i]!=']')
            {
                sta.push(s[i]);
                i++;
                continue;
            }
            if(ch=='{' && s[i]!='}')
            {
                sta.push(s[i]);
                i++;
                continue;
            }
            sta.pop();
            i++;
        }
        if(!sta.empty())
            return false;
        return true;
    }
};

发表于 2018-09-11 15:45:46 回复(0)

啊哟嘿

public class Solution {
public boolean isValid(String s) {
if(s==null||s.length() stack = new LinkedList();
char[] charArray = s.toCharArray();
for (int i = 0; i < charArray.length; i++) {
if(stack.size()==0){
stack.add(charArray[i]);
continue;
}else if (getReverse(stack.getLast())=='x') {
//栈顶元素一定为右开元素
return false;
}else if (getReverse(stack.getLast())!=charArray[i]) {
stack.add(charArray[i]);
}else {
stack.removeLast();
}
}
return stack.size()==0?true:false;
}
//用来求闭合符号
public char getReverse(char sympol){
char result = 'x' ;
switch (sympol) {
case '(':
result = ')';
break;
case '[':
result = ']';
break;
case '{':
result = '}';
break;
}
return result;
}
}

编辑于 2017-12-30 23:12:25 回复(0)

LinuX18

class Solution {
public:
    // 使用栈解决
    bool isValid(string s) 
    {
      stack<char> st;
      for(char chr : s)
     {
       if(chr=='(' || chr=='[' || chr=='{')
            st.push(chr);
       else if(chr == ')')
       {
           if(st.empty() || st.top()!='(')
                return false;
            st.pop();
       }
       else if( chr == ']')
       {
           if(st.empty() || st.top() !='[')
             return false;
            st.pop();
       }
       else if( chr == '}')
       {
           if(st.empty() || st.top() != '{')
             return false;
            st.pop();
       }
    }
    return st.empty();  
    }
};

发表于 2017-07-10 21:03:02 回复(2)

后劲好大

// 蛮简单的题目哈~
import java.util.Stack;
public class Solution {
    public boolean isValid(String s) {
        if(s == null || s.length() == 0)
			return true;
		
		Stack<Character> stack = new Stack<>();
		for(int i = 0; i < s.length(); i++){
			if(s.charAt(i) != '(' && s.charAt(i) != ')' && s.charAt(i) != '[' 
				&& s.charAt(i) != ']' && s.charAt(i) != '{' && s.charAt(i) != '}'){
				return false;
			}
			if(s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[')
				stack.push(s.charAt(i));
			else{
				if(stack.isEmpty() || (s.charAt(i) == ')' && stack.pop() != '(')
					|| (s.charAt(i) == '}' && stack.pop() != '{')
					|| (s.charAt(i) == ']' && stack.pop() != '['))
					return false;
			}
		}
		if(stack.isEmpty())
			return true;
		else
			return false;
    }
}

发表于 2017-07-02 10:19:44 回复(1)

Java

廖湘浩

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)

Java

执子一白

这道题借助栈来实现思路还是蛮简单的
左括号入栈，遇到右括号出栈，并比对是否匹配
最后判断是否栈空，栈空则符合语法

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */

    public boolean isValid (String s) {
        // write code here
        //借助栈来实现
        Stack<Character> stack=new Stack<>();
        char[] charArray=s.toCharArray();

        for(int i=0;i<charArray.length;i++){
            char curChar=charArray[i];
            if(curChar=='('||curChar=='{'||curChar=='['){
                //左括号直接入栈
                stack.push(curChar);
            }else{
                //否则出栈比对
                if(stack.isEmpty()){
                    return false;
                }
                char popChar=stack.pop();
                if(curChar==')'&&popChar!='('){
                    return false;
                }
                if(curChar==']'&&popChar!='['){
                    return false;
                }
                if(curChar=='}'&&popChar!='{'){
                    return false;
                }
            }

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



     }
}

发表于 2020-11-28 13:57:01 回复(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)

Core123

    def isValid(self , s ):
        stack = []
        dic = {"(":")", "{":"}","[":"]"}
        for i in s:
            if i in dic:stack.append(i)
            elif len(stack)==0&nbs***bsp;dic[stack.pop()]!=i:return False
        return len(stack)==0

发表于今天 01:27:24 回复(0)