力扣20:有效的括号

题目

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

有效字符串需满足：

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

思路

有效的括号字符串一定是先几个左括号然后按照相反的顺序再添加几个右括号，所以最先出现的左括号反而是最后出去的。也就是先进后出机制这不就很容易想到我们的栈了吗。想到用什么数据结构了这道题的代码就很简单了。只需要进行判断即可。

代码

class Solution {
public:bool isValid(string s) {stack<char> st;for(auto& ch : s){if(ch == '(' || ch == '[' || ch == '{'){st.push(ch);}else if (!st.empty() && ch == ')' && st.top() == '('){st.pop();}else if(!st.empty() && ch == ']' && st.top() == '['){st.pop();}else if(!st.empty() && ch == '}' && st.top() == '{'){st.pop();}else{return false;}}if(st.empty()){return true;}return false;}
};