Day26 代码随想录打卡|栈与队列篇---有效的括号

题目（leecode T20）：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

方法：括号匹配是栈的经典应用，首先我们要分析括号不匹配的几种情况：

1：{[(}]} 这首情况是由于括号类型不匹配所造成的

2：(([])  这种情况是左边多了一个括号，右边无法和他匹配

3：{()}) 这种情况是右边多了一个括号，左边无法和他匹配

分析了这三种情况，我们就可以得出相应的写法，在左边括号入栈时，我们输入与其相匹配的右括号，这样在分析右括号时我们直接进行判断相等即可，更加容易操作。在右边括号匹配时，如果出现栈已经为空，则是出现了第三种错误，右边多了括号；如果出现括号与当前栈中元素不一致，则出现了第一种错误，类型不匹配；如果已经匹配完，但栈不为空，还有元素，则出现了第二种错误，左边多了括号。因此我们处理完字符串后，只需要判断当前栈是否为空，如果为空的话就说明已经匹配成功；如果栈不为空的话，就说明不成功。

题解：
 

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() || st.top() != s[i]) return false; //第一三种情况
            else st.pop();
        }
        return st.empty();            //第二种情况
    }
};