#include <bits/stdc++.h>

using namespace std;

// Problem 20. Valid Parenthesis
// Easy

// Given a string s 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.
// Every close bracket has a corresponding open bracket of the same type.

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

        if (s.size() % 2 != 0)
            return false;

        for (auto c: s)
        {
            if (c == '(' || c == '{' || c == '[') { m_stack.push(c); continue; }
            else
            {
                if (m_stack.empty()) return false;
                else if (c == ')') { if (m_stack.top() == '(') m_stack.pop(); else return false; }
                else if (c == '}') { if (m_stack.top() == '{') m_stack.pop(); else return false; }            
                else if (c == ']') { if (m_stack.top() == '[') m_stack.pop(); else return false; }
            }
        }
        if (m_stack.empty()) return true;
        return false;
    }
};

int main(void)
{
    vector<tuple<string, bool>> testCases = {
        {"()", true},
        {"(]", false},
        {"({[()]})", true},
        {"()[]{[()]})", false},
        {"((", false},
        {"}{", false},
    };

    for (auto test: testCases)
    {
        const string& str = get<0>(test);
        bool expected = get<1>(test);
        
        Solution s;
        bool result = s.isValid(str);
        cout << str << endl;        
        cout << "result: " << (result == true ? "true" : "false")
             << " expected: " << (expected == true ? "true" : "false") << endl;
        if (expected != result)
            cout << "Failed\n";        
        cout << "--------------\n";
    }
    return 0;
}