给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
代码语言：javascript复制输入：s = "()"
输出：true示例 2：
代码语言：javascript复制输入：s = "()[]{}"
输出：true示例 3：
代码语言：javascript复制输入：s = "(]"
输出：false提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
首先要理解题意，什么才是题目中描述的有效括号，比如s = "({)[]}", 如下图，把同类型的括号单独按顺序拆出来，每种类型的括号都是能闭合的，但是s并不是合法的。
因为最先和'{'闭合的是')'，违背了 左括号必须用相同类型的右括号闭合 这个原则。而且上面的这种拆法本身也违反了 左括号必须以正确的顺序闭合的原则。
很多同学都因为没有理解透题意面试的时候没有把这道题正确的做出来，非常可惜。
理清题意，只需要借助栈，遍历字符串当元素为'('、'{'、'['就压栈，遇到')'、'}'、']'就和栈顶元素比较，能组成合法括号就弹出栈顶元素，不能组成合法括号就返回false，直到遍历完字符串，栈为空就返回true。整个匹配过程就像我们平时玩的小游戏消消乐。
举个简单的例子，s = "({}[])"，匹配过程如下图：
遍历完s以后，栈是空的，这就说明字符串s是合法的。
代码语言：javascript复制class Solution {
public:
//判断两个字符能否组成合法的括号
bool isMatch(char& left, char& right) {
if (left == '(' && right == ')') {
return true;
} else if (left == '{' && right == '}') {
return true;
} else if (left == '[' && right == ']') {
return true;
} else {
return false;
}
}
bool isValid(string s) {
stack<char> st_ch;
int s_len = s.length();
//s的长度为奇数,一定是非法的
if (s_len % 2 != 0) {
return false;
}
for (auto& ch:s) {
//遇到'('、'{'、'['就压栈
if (ch == '(' || ch == '{' || ch == '[')
st_ch.push(ch);
//遇到')'、'}'、']'就和栈顶元素比较，能组成合法括号就弹出栈顶元素
//栈的操作一定要小心，不要对空栈进行pop操作
else if (!st_ch.empty() && isMatch(st_ch.top(), ch))
st_ch.pop();
else
return false;
}
if (st_ch.empty()) {
return true;
}
return false;
}
};
