Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.
这道题就是判断括号的配对的正确与否，使用stack即可解决。主要思路如下：遍历字符串即可， 1）遇到左括号，直接入栈； 2）遇到右括号，判断右括号与栈顶元素是否配对； a) 假如不配对，表示整体不配对； b) 假如配对，出栈。 3）遍历结束的时候，假如栈不空，表示不配对，否者配对成功。
建议和leetcode 32. Longest Valid Parentheses 最长有效括号长度和 leetcode 678. Valid Parenthesis String 有效括号的判断 一起学习
代码如下：
import java.util.ArrayList; import java.util.List; public class Solution { public boolean isValid(String s) { boolean res=true; if(s==null || s.length()<=0) return res; if(s.length()%2==1) return false; List<Character> stack=new ArrayList<Character>(); for(int i=0;i<s.length();i++) { char n=s.charAt(i); if(n=='(' || n=='[' || n=='{') stack.add(n); else if(n==')' || n==']' || n=='}') { if(stack.isEmpty()) { //第一个字符就是闭合字符,比如] } ) res=false; break; } if(stack.get(stack.size()-1)==getDui(n)) stack.remove(stack.size()-1); else { //匹配错误 res=false; break; } } else { //出现了不该出现的字符 res=false; break; } } //stack不为空必然就是不匹配，比如 (( if(res==true && stack.size()>0) res=false; return res; } private Character getDui(char n) { char res=' '; switch (n) { case ')': res='('; break; case ']': res='['; break; case '}': res='{'; break; default: break; } return res; } }C++的代码如下：
#include <iostream> #include <stack> using namespace std; class Solution { public: bool isValid(string s) { if (s.length() <= 0) return true; stack<char> my; for (int i = 0; i < s.length(); i++) { char a = s[i]; if (a == '(' || a == '{' || a == '[') my.push(a); else if (a == ')' || a == '}' || a == ']') { if (my.empty()) return false; else { char b = getDuiYing(a); cout << a << " " << b << endl; if (my.top() == b) my.pop(); else return false; } } } return my.empty(); } char getDuiYing(char a) { switch (a) { case ')': return '('; case ']': return '['; case '}': return '{'; default: return a; } } };