有效括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
示例 1:
- 输入: "()"
- 输出: true
示例 2:
- 输入: "()[]{}"
- 输出: true
示例 3:
- 输入: "(]"
- 输出: false
示例 4:
- 输入: "([)]"
- 输出: false
示例 5:
- 输入: "{[]}"
- 输出: true
思路
一看就是用栈做的
只要遍历将字符串压栈，然后再出栈，如果和之前的字符串相比一致，那么说明可以配对
但是，题目的考察点在于：如何找出（模拟出）不匹配的情况
不匹配的情况
不管怎么组合，所有不匹配的情况都可以归类为以下三种：
-
第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
-
第二种情况，括号没有多余，但是括号的类型没有匹配上。
-
第三种情况，字符串里右方向的括号多余了，所以不匹配。
举一些例子：
)(属于情况3，即右括号多余，因为左边没有左括号与其对应
[(])属于情况2，即括号类型不匹配，虽然括号数量没有多也没有少
...等等还有很多，反正仔细去看都绕不开这三种情况
用栈模拟不匹配情况
显然我们是要遍历括号串，将其压入栈中的
注意，每次我们压栈的括号类型要与当前遍历到的相反，这样在出栈比对的时候就比较方便
如果不是很理解我就这么说吧
满足有效括号的括号串都是偶数个数，且两两对应
如果按上面的操作就会有以下效果
例如，一有效括号如：([])
======先看栈顶，没有与当前左括号匹配的，把相反方向括号压栈
↓
([])
栈
)
======先看栈顶，没有与当前左中括号匹配的，把相反方向括号压栈
↓
([])
栈
])
======先看栈顶，栈顶与当前右中括号匹配的，pop栈顶
↓
([])
栈
])
======先看栈顶，栈顶与当前右括号匹配的，pop栈顶
↓
([])
栈
)
//遍历结束，栈空，完全匹配，有效括号
以上就是栈在该问题中的使用方式
即在遍历结束时或过程中，通过栈的状态来判断括号串是否有效
实际上对应三种不匹配情况，栈的状态也会有三种
以上面的括号为例
动画如下：
第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
从这里可以看出，往栈压入相反方向括号的好处：能够与现有的括号进行比较
因为我们在压栈之前都要先判断当前遍历值与栈顶元素是否匹配，只有有效括号串能够在遍历结束时完全匹配（因为有效括号串是对称的）
代码
步骤：
（0、剪枝，如果括号串是奇数个数，直接false）
1、创建栈，遍历括号串遇到什么括号就把相反方向的括号push进栈
2、判定栈是否为空或者栈顶与当前遍历值不匹配，满足则返回false
3、遍历结束，判断当前栈内是否为空，为空则是有效括号，还有东西则表明没有完全匹配上，false
class Solution {
public:
bool isValid(string s) {
//剪枝
if(s.size() % 2 != 0){
return false;
}
//创建栈
stack<char> st;
//遍历括号串
for(int i = 0; i < s.size(); ++i){
if(s[i] == '('){
st.push(')');
}else if(s[i] == '['){
st.push(']');
}else if(s[i] == '{'){
st.push('}');
}else if(st.empty() || s[i] != st.top()){//遍历过程中栈空或者栈顶与当前遍历值不匹配
return false;
}else{//栈顶与当前遍历值相等，弹出栈顶值
st.pop();
}
}
return st.empty();//遍历完成，判断当前栈中是否还有元素剩余，没有就是有效括号
}
};
