题目

题目链接：20. 有效的括号

---

思路

有效括号的匹配问题和栈的出入问题很相似且匹配；
括号匹配问题可以从最内部的括号开始匹配：比如[ ( { } ) ]从 { } 开始匹配，只要是成对，表示匹配成功，继续匹配下一对！
可是关键问题是，如何找到最里面的括号对匹配呢？
我们可以用栈来帮助我们，当我们遍历字符串 s 时候，碰到左括号就入栈，碰到右括号就拿出栈的左括号来匹配，这样不就可以成对匹配了嘛！
并且由于栈是后进先出的结构，也就解决了从字符串内部括号匹配的问题！

---

思路：
1.遍历字符串，遇到左括号入栈，同时字符指针++；遇到右括号出栈，同时记得弹栈，得到左括号，和右括号比较；
2. 当遍历结束后，可能字符串本身为空，就直接结束；
3. 可能直接匹配成功就结束；
4. 可能栈不空，还剩左括号，也直接结束！

class Solution {
public:bool isValid(string s) {//遍历字符串,获取每一个字符int size = s.size();stack<char> st;for(int i = 0;i<size;i++){char ch = s[i];//碰到左符号入栈，如：({[if(ch == '(' ||ch == '[' || ch == '{') st.push(ch);//碰到右符号,如：]})出栈左符号得到栈顶与由符号匹配else{if(st.empty()) //假如没有左括号，此时，栈为空return false;//到这里说明栈不空，取栈顶元素和右括号匹配char top = st.top();st.pop();if  (top == '(' && ch != ')') return false;if  (top =='[' &&ch != ']' ) return false;if  (top == '{' &&ch != '}') return false;}}//遍历完字符串后，栈为空，说明左右字符匹配完，则匹配成功；//或者说字符串本身就为空，直接返回false//可能栈不空，还剩左括号，也直接结束！返回的是falsereturn st.empty();       }  
};