括号匹配是使用栈解决的经典问题。
题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号
可能的三种情况：
第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
class Solution { public: bool isValid(string s) { if(s.size()%2!=0) return false;//为奇数则一定不匹配 stack<char> st;//也可以用int 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() || st.top()!=s[i]) return false;// else st.pop(); //第三种情况：右括号多了 //第二种情况：左右括号不匹配 } return st.empty();//第一种情况 } };
在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，更加简单