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.
#include <iostream>
#include <string>
#include <stack>
#include <map>
using namespace std;
class Solution {
private:
map<char,char> pairs;
stack<int> pstack;
public:
Solution()
{
pairs[‘)‘] = ‘(‘;
pairs[‘}‘] = ‘{‘;
pairs[‘]‘] = ‘[‘;
}
bool isValid(string s) {
int len = s.length();
if(len%2)return false;
int i = 0;
map<char,char>::iterator it;
char sen;
for(i = 0; i < len; i++){
it = pairs.find(s[i]);
if(it == pairs.end()){
pstack.push(s[i]);
continue;
}
sen = it ->second;
if(!pstack.empty()){
char tmp = pstack.top();
if(tmp == sen){
pstack.pop();
}else{
return false;
}
}else{
return false;
}
}
if(pstack.empty())return true;
return false;
}
};
int main()
{
Solution s = Solution();
cout << s.isValid("[{}]{{}()}") << endl;
return 0;
}
原文:http://www.cnblogs.com/zhutianpeng/p/4245314.html