20.有效的括号

题目描述

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

解法一：stack

这道题目是典型的堆栈数据结构的应用，虽然思路很清晰，代码也很简单，但是要注意逻辑的严谨性。尤其是在判断栈顶元素是否匹配之前，要先判断栈是否为空。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isValid(const std::string& s) {
        std::stack<char> st;
        for (int i = 0; i < s.length(); ++i) {
            char c = s[i];
            if (c == '(' || c == '{' || c == '[') {
                st.push(c);
            } else {
                if (st.empty()) return false;
                if (c == ')' && st.top() != '(') return false;
                if (c == '}' && st.top() != '{') return false;
                if (c == ']' && st.top() != '[') return false;
                st.pop();
            }
        }
        return st.empty();
    }
};