给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
思路：
用栈实现，左侧括号就进栈，右侧括号就弹栈并判断
从他人代码中学会了一种优化
即奇数个直接返回false
具体代码
#include<string>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
bool isValid(string s) {
vector<char> stack;
//奇数必定不匹配，直接返回
if(s.size() % 2) return false;
for(int i = 0; i < s.size(); i++){
//左侧括号，压栈
if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
stack.push_back(s[i]);
}
else{
//如果栈为空，无法弹
if(stack.empty()){
return false;
}
//如果弹栈内容与读入内容不匹配
if(stack.back() == '(' && s[i] != ')'){
return false;
}
else if(stack.back() == '[' && s[i] != ']'){
return false;
}
else if(stack.back() == '{' && s[i] != '}'){
return false;
}
else{
//匹配，直接弹栈
stack.pop_back();
}
}
}
//如果全部匹配，返回true
return stack.empty();
}
int main(){
//测试空
cout << isValid("") << endl;
//测试仅左侧
cout << isValid("[") << endl;
//测试仅右侧
cout << isValid("]") << endl;
//稍长字符串测试
cout << isValid("[({{{{}}}})]") << endl;
//不匹配字符串
cout << isValid("[(])]") << endl;
return 0;
}
