题目描述

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

解法一：stack

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

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