/*
Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’,
determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: “()”
Output: true
Example 2:

Input: “()[]{}”
Output: true
Example 3:

Input: “(]”
Output: false
Example 4:

Input: “([)]”
Output: false
Example 5:

Input: “{[]}”
Output: true
*/

Use the stack to save the left half parenthesis, use the brackets to make detailed judgment, and out of the stack.Pay attention to the empty data

class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2 != 0){
            return false;
        }
        stack<char> q;
        for(int i = 0; i < s.size(); i++){
            if(s.at(i) == '(' || s.at(i) == '[' || s.at(i) == '{'){
                q.push(s.at(i));   
            }else if(s.at(i) == ')'){
                if(q.empty()){
                    return false;
                }
                char c = q.top();
                q.pop();
                if(c != '('){
                    return false;
                }
            }else if(s.at(i) == ']'){
                if(q.empty()){
                    return false;
                }
                char c = q.top();
                q.pop();
                if(c != '['){
                    return false;
                }
            }else if(s.at(i) == '}'){
                if(q.empty()){
                    return false;
                }
                char c = q.top();
                q.pop();
                if(c != '{'){
                    return false;
                }
            }
        }
        if(q.empty()){
            return true;
        }else{
            return false;
        }
    }
};