【力扣】用栈判断有效的括号

有效的括号原题地址

方法一：栈

对于特殊情况，当字符串的长度为奇数时，一定不是有效的括号。

对于一般情况，考虑使用数据结构栈。

遍历字符串，

1. 遇到左括号时，就入栈。
2. 遇到右括号时，
   1. 若栈顶元素是与这个右括号匹配的左括号，就成功匹配了一对括号，出栈即可。
   2. 若栈顶元素不是与这个右括号匹配的左括号，或者栈为空，就匹配失败，不是有效的括号。

当字符串遍历完时，

1. 若栈不为空，说明还有左括号未匹配，不是有效的括号。
2. 若栈为空，说明所有括号都匹配完了，是有效的括号。

由于题目描述说明，字符串中的字符不是左括号就是右括号，所以可以使用 key-value 模型的哈希结构来存储键值对，其中右括号为键，左括号为值。这样，对于每个字符，只需判断其是否在哈希表中，就能判断是左括号还是右括号。遇到右括号时，可以直接在哈希表中查询其对应的左括号。

C++ 中，建议使用 unordered_map<char, char> 来存储键值对，并定义成静态的类成员变量，因为在整个程序运行期间只需要存在一份。

[](){()}
^
入栈 -> [[](){()}^
出栈[](){()}^入栈 -> ([](){()}^出栈[](){()}^入栈 -> {[](){()}^入栈 -> {([](){()}^出栈 -> {[](){()}^出栈，此时栈为空，是有效的括号

// 方法一：栈
class Solution
{
public:bool isValid(string s){// 字符串长度为奇数if (s.size() % 2){return false;}stack<char> st;for (auto ch : s){// 右括号出栈匹配if (pairs.count(ch)){// 栈为空或不匹配if (st.empty() || st.top() != pairs[ch]){return false;}st.pop();}else // 左括号入栈{st.push(ch);}}// 栈中是否还有没匹配的左括号return st.empty();}
private:static unordered_map<char, char> pairs;
};unordered_map<char, char> Solution::pairs
{{')','('},{']','['},{'}','{'}
};