Valid Parentheses 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.
有效的括号序列 给定一个字符串所表示的括号序列，包含以下字符： ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’， 判定是否是有效的括号序列。
样例 括号必须依照 “()” 顺序表示， “()[]{}” 是有效的括号，但 “([)]”则是无效的括号。
标签 栈 谷歌 相关题目 中等 生成括号
C++: //Version 1 #include <iostream> #include <stack> using namespace std; bool IsLeftParentheses(char c) { return (c == '{' || c == '[' || c == '('); } bool IsMatch(char left, char c) { if(left == '{') return c == '}'; if(left == '[') return c == ']'; if(left == '(') return c == ')'; return false; } bool MatchParentheses(const char* p) { stack<char> s; char cur;//current while (*p) { cur = *p; if(IsLeftParentheses(cur)){ s.push(cur);//将左括号压栈 }else{//当前为右括号：看当前栈s中是否有与之匹配的左括号（栈顶s.top()） if(s.empty() || !IsMatch(s.top(), cur))//若栈已经为空，说明缺少左括号与之匹配 return false; s.pop();//若与栈顶（离cur最近的左括号）匹配，则将与之匹配的左括号从栈s中弹出。 } p++; } return s.empty();//看最后栈s中有无未匹配的左括号 -> 若有，则括号不匹配。 } int main(int argc, const char * argv[]) { // insert code here... char* p = "(){}[]"; bool match = MatchParentheses(p); if(match) cout << p << "括号匹配！" << endl; else cout << p << "括号不匹配！" << endl; return 0; } //Version 2 class Solution { public: /** * @param s A string * @return whether the string is a valid parentheses */ bool isValidParentheses(string& s) { // Write your code here vector<char> stack; stack.push_back(' '); for (int i = 0; i < s.size(); i++) { char item = s[i]; if (item == '(' || item == '[' || item == '{') { stack.push_back(item); } if (item == ')') { if (stack.back() != '(') { return false; } stack.pop_back(); } if (item == ']') { if (stack.back() != '[') { return false; } stack.pop_back(); } if (item == '}') { if (stack.back() != '{') { return false; } stack.pop_back(); } } if (stack.back() != ' ') { return false; } return true; } }; // version 3 class Solution { public: /* 题意：输入一个只包含括号的字符串，判断括号是否匹配 模拟堆栈，读到左括号压栈，读到右括号判断栈顶括号是否匹配 */ bool isValidParentheses((string s) { int len = s.length(); vector<char> stack; for (int i = 0; i < len; i++) { // 左括号压栈 if (s[i] == '(' || s[i] == '[' || s[i] == '{') stack.push_back(s[i]); else { // 右括号出栈 if (stack.empty()) return false; char top = stack[stack.size() - 1]; if (s[i] == ')' && top != '(') return false; if (s[i] == ']' && top != '[') return false; if (s[i] == '}' && top != '{') return false; stack.pop_back(); } } // 栈中无多余左括号 if (stack.size() > 0) return false; return true; } }; Java： //Version 1 public class Solution { public boolean isValidParentheses(String s) { Stack<Character> stack = new Stack<Character>(); for (Character c : s.toCharArray()) { if ("({[".contains(String.valueOf(c))) { stack.push(c);//将左括号压栈 } else { if (!stack.isEmpty() && is_valid(stack.peek(), c)) {//若stack栈顶与当前c匹配 stack.pop();//将栈顶的左括号弹出 } else { return false; } } } return stack.isEmpty(); } private boolean is_valid(char c1, char c2) { return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}') || (c1 == '[' && c2 == ']'); } } // version2 public class Solution { /** * @param s A string * @return whether the string is a valid parentheses */ public boolean isValidParentheses(String s) { // Write your code here Stack<Character> stack = new Stack<>(); for (char c : s.toCharArray()) { if (c == '(' || c == '[' || c == '{') { stack.push(c); } if (c == ')') { if (stack.isEmpty() || stack.pop() != '(') { return false; } } if (c == ']') { if (stack.isEmpty() || stack.pop() != '[') { return false; } } if (c == '}') { if (stack.isEmpty() || stack.pop() != '{') { return false; } } } return stack.isEmpty(); } }