描述

给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

数据范围：字符串长度 0\le n \le 100000≤n≤10000
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

示例1

输入： 
"["
复制
返回值： 
false
复制

示例2

输入： 
"[]"
复制
返回值： 
true
复制

解题思路：
1、利用栈先进后出的机制，将左括号依次入栈，遇到右括号后从栈顶取元素比较是否匹配，不匹配则不合法；
匹配则继续轮询，直到最后所有的括号都出栈则为合法括号序列。 
class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool isValid(string s) {
        // write code here
        stack<char>st;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            if (st.empty() || s[i] == '[' || s[i] == '{' || s[i] == '(') {
                st.push(s[i]);
                continue;
            }
            if (s[i] == ']') {
                if (st.top() == '[') {
                    st.pop();
                } else {
                    return false;
                }
            } else if (s[i] == ')') {
                if (st.top() == '(') {
                    st.pop();
                } else {
                    return false;
                }
            } else if (s[i] == '}') {
                if (st.top() == '{') {
                    st.pop();
                } else {
                    return false;
                }
            }

        }
        return (st.empty());
    }
};