题意：
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. （Easy）
这道题是8月5号做的，居然没有写博客当时...最近真是乱了，顺便整理了一下做题日志...
分析：
比较简单，弄一个栈，左括号压栈，右括号匹配了就弹栈，不匹配或没有元素了return false, 一遍走完了判断栈是否为空。
class Solution {
public:
bool isValid(string s) {
if (s.size() == ) {
return true;
}
stack<char> sta;
sta.push(s[]);
for (int i = ; i < s.size(); ++i) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
sta.push(s[i]);
continue;
}
if ( (s[i] == ')' || s[i] == ']' || s[i] == '}') && sta.empty() ) { // "()]"
return false;
}
if (s[i] == ')') {
if (sta.top() == '(') {
sta.pop();
continue;
}
else {
return false;
}
}
if (s[i] == ']') {
if (sta.top() == '[') {
sta.pop();
continue;
}
else {
return false;
}
}
if (s[i] == '}') {
if (sta.top() == '{') {
sta.pop();
continue;
}
else {
return false;
}
}
return false;
}
if (sta.empty()) {
return true;
}
else {
return false;
}
}
};
第一次提交的时候忘了sta.empty()也return false 的情况；
其次，代码冗余太多，写的有点长，优化一下。
class Solution {
public:
bool isValid(string s) {
if (s.size() == ) {
return true;
}
stack<char> sta;
sta.push(s[]);
for (int i = ; i < s.size(); ++i) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
sta.push(s[i]);
continue;
}
else {
if ( sta.empty() ) { // "()]"
return false;
}
if (s[i] == ')' && sta.top() != '(') {
return false;
}
if (s[i] == ']' && sta.top() != '[') {
return false;
}
if (s[i] == '}' && sta.top() != '{') {
return false;
}
sta.pop();
}
}
return sta.empty();
}
};