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.
Solution:
Use stack. When we meet a left parentheses, we push it into the stack. When we meet a right parentheses, we will return false if the stack is empty, otherwise, we will pop the top of the stack to find if it is the corresponding left parentheses.
1 class Solution { 2 public: 3 bool isValid(string s) { 4 stack<char> st; 5 for(int i = 0; i < s.size(); i++){ 6 if(s[i] == ‘(‘ || s[i] == ‘{‘ || s[i] == ‘[‘){ 7 st.push(s[i]); 8 }else if(s[i] == ‘)‘ || s[i] == ‘}‘ || s[i] == ‘]‘){ 9 if(st.empty()){ 10 return false; 11 }else{//只需判断false的情况，最后再pop就可以了 12 if(s[i] == ‘)‘ && st.top() != ‘(‘) return false; 13 if(s[i] == ‘]‘ && st.top() != ‘[‘) return false; 14 if(s[i] == ‘}‘ && st.top() != ‘{‘) return false; 15 st.pop(); 16 } 17 } 18 } 19 //return true;此时不能直接return true，因为stack里可能会有剩余的左括号 20 return st.empty(); 21 } 22 };
原文：http://www.cnblogs.com/93scarlett/p/6362009.html