leetcode20. 有效的括号 [简单题]

题目

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

思路

典型的栈问题，数据结构书中都有用栈来作括号匹配的问题。

①字符串长度为奇数，直接返回false

②“( ] )”，当有这样的右括号时，也让他入栈，最后判断栈非空，则返回 false;

③“( ) { } } {”，

④“{ [ ] }”，

代码

class Solution {
public:bool isValid(string s) {int len = s.length();bool flag;if (len % 2 != 0)flag = false;stack<char> st;int i;    for (i = 0; i < len; i++) {// 遇到左括号，入栈if (s[i] == 40 || s[i] == 91 || s[i] == 123) {  st.push(s[i]);}// 遇到右括号，取栈顶元素，看是否匹配。匹配则出栈，不匹配则入栈char a;if (s[i] == 41 || s[i] == 93 || s[i] == 125) {  // 遇到右括号时，栈中无元素，则直接返回falseif (st.empty()) {flag = false;break;}if (!st.empty()) {a = st.top();}if ((a == 40 && s[i] == 41) || (a == 91 && s[i] == 93) || (a == 123 && s[i] == 125)) {st.pop();   // 匹配则出栈}else{st.push(s[i]);  // 不匹配则入栈}}}if (i != len) {return flag;}if (i == len && st.empty())flag = true;return flag;}
};

答案思路：

建立map，键为右括号，值为左括号。

unordered_map<char, char> pairs = {{')', '('},{']', '['},{'}', '{'}
};