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 class Solution { 2 public: 3 bool isValid(string s) { 4 int length=s.length(),i=1,temp=0; 5 if(length%2!=0||length==0) return false; 6 map<int,int> dic; 7 dic[40]=41; 8 dic[91]=93; 9 dic[123]=125; 10 stack<char> match; 11 match.push(s[0]); 12 while(!match.empty()&&i<length){ 13 temp=match.top(); 14 if(dic.find(temp)==dic.end()) return false; 15 if(s[i]==dic[temp]){i++; match.pop();} 16 else match.push(s[i++]); 17 } 18 if(match.empty()) return true; 19 else return false; 20 21 } 22 };
原文：http://www.cnblogs.com/LUO77/p/5047560.html