#include <iostream>
#include <stack>
#include <map>
using namespace std;

class Solution
{
    static const inline map<char, char> parenparenthesises = {
        { ')', '(' },
        { '}', '{' },
        { ']', '[' }
    };
public:
    bool isValid(string s)
    {
        stack<char> nested_braces;
        for (const char ch : s)
        {
            auto it = parenparenthesises.find(ch);
            if (it == parenparenthesises.end())
            {
                nested_braces.push(ch);
            }
            else if (!nested_braces.empty() && ch == it->first && nested_braces.top() == it->second)
            {
                nested_braces.pop();
            }
            else
            {
                return false;
            }
        }

        return nested_braces.empty();
    }
};