20.valid-parentheses 有效的括号

利用stack，括号匹配时pop()。

#include <stack>
#include <string>
using std::stack;
using std::string;
class Solution {
  public:
    bool isValid(string s) {
        stack<char> st;
        char temp;
        for (char c : s) {
            if (c == '(' || c == '{' || c == '[')
                st.push(c);
            else {
                if (st.empty())
                    return false;
                if (c == ')') {
                    temp = st.top();
                    st.pop();
                    if (temp != '(')
                        return false;
                } else if (c == '}') {
                    temp = st.top();
                    st.pop();
                    if (temp != '{')
                        return false;
                } else {
                    temp = st.top();
                    st.pop();
                    if (temp != '[')
                        return false;
                }
            }
        }
        if (st.empty())
            return true;
        else
            return false;
    }
};

一种更简洁的写法，遇到左括号，入栈对应的右括号

#include <stack>
#include <string>
using std::stack;
using std::string;
class Solution {
  public:
    bool isValid(string s) {
        stack<char> st;
        char temp;
        for (char c : s) {
            if (c == '(')
                st.push(')');
            else if (c == '[')
                st.push(']');
            else if (c == '{')
                st.push('}');
            //碰到右括号时栈为空或者上一个字符不是对应的左括号
            else if (st.empty() || c != st.top())
                return false;
            else
                st.pop(); //括号匹配时出栈
        }
        return st.empty();
    }
};