问题：
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 String
方法1：（效率低）
#include <stack> #include <string> class Solution { public: bool isValid(string s) { stack<char> mystack; for(int i=0; s[i]!=‘\0‘; i++){ char c=s[i]; switch(c){ case ‘(‘: case ‘[‘: case ‘{‘: mystack.push(c); break; case ‘)‘: if(mystack.empty() || mystack.top()!=‘(‘) return false; else mystack.pop(); break; case ‘]‘: if(mystack.empty() || mystack.top()!=‘[‘) return false; else mystack.pop(); break; case ‘}‘: if(mystack.empty() || mystack.top()!=‘{‘) return false; else mystack.pop(); break; } } return mystack.empty(); } };
方法2：（效率低）
#include <stack> #include <string> class Solution { public: bool isValid(string s) { stack<char> mystack; map<char,char> mymap; mymap.insert(pair<char,char>(‘(‘,‘)‘)); mymap.insert(pair<char,char>(‘[‘,‘]‘)); mymap.insert(pair<char,char>(‘{‘,‘}‘)); for(int i=0; s[i]!=‘\0‘; i++){ char c=s[i]; switch(c){ case ‘(‘: case ‘[‘: case ‘{‘: mystack.push(c); break; case ‘)‘: case ‘]‘: case ‘}‘: if(!mystack.empty()){ if(c!=mymap[mystack.top()]) return false; mystack.pop(); //pop()的返回值为void } else return false; break; } } return mystack.empty(); } };
该题别人用Java写的：https://segmentfault.com/a/1190000003481208
C++栈的申明：http://zhidao.baidu.com/link?url=DvEEXh4U47QLJnjmv6rAeMVk1V7A_5LCii42ctj8m2ehl1MepSy0w9BSWevmfuHwlstx0D60kvBNRvAoQgFtjK
C++栈操作：http://www.169it.com/article/2839007600903800247.html
C++ map操作：http://blog.sina.com.cn/s/blog_61533c9b0100fa7w.html
原文：http://www.cnblogs.com/calvin2/p/5964633.html