class Solution {
public:
    bool isValid(string s) {
        stack<char> sta;

        for(char c : s){
            if(c == '(' || c == '[' || c == '{'){
                sta.push(c);
            } else {
                if(sta.empty()){
                    return false;
                }
                int t = sta.top();

                if(c == ')' && t != '('){
                    return false;
                } else if (c == ']' && t != '['){
                    return false;
                } else if (c == '}' && t != '{'){
                    return false;
                }
                sta.pop();
            }
        }

        return sta.empty(); 
    }
};