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.
Subscribe to see which companies asked this question
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | class Solution {public: bool isValid(string s) { stack<char> stk; int len = s.size(); if(0 >= len) return false; for(int i = 0; i < len; ++i){ if(s[i] == ‘(‘ || s[i] == ‘[‘ || s[i] == ‘{‘){ stk.push(s[i]); } else{ if(stk.empty()){ return false; } else{ if(match(stk.top(),s[i])){ stk.pop(); } else{ return false; } } } } if(stk.empty()) return true; else return false; } bool match(char c1, char c2){ switch(c1){ case ‘(‘: return c2 == ‘)‘; case ‘{‘: return c2 == ‘}‘; case ‘[‘: return c2 ==‘]‘; default: return false; } }}; |
原文：http://www.cnblogs.com/zhxshseu/p/13d93dcf02420ae4542b294a754d818d.html