#include <iostream>
#include <queue>
#include <stack>

using namespace std;

// Cases:
// )()
// ()(
// )()(

// Run-time complexity O(n)
// Memory complexity O(1)
bool isCorrect(const string& sChars){
    int sum = 0;
    for (char c : sChars){
        if (c == '(')
            ++sum;
        if  (c == ')')
            --sum;
        if (sum < 0)
            return false;
    }

    if (sum != 0)
        return false;
    else
        return true;
}

// Run-time complexity O(n)
// Memory complexity O(n)
bool isCorrect(const string& sChars){

    stack<char> stackChars;

    for (char c : sChars){
        if (c == '(')
            stackChars.push(c);
        if (c == ')')
            if (!stackChars.empty())
                stackChars.pop();
            else
                return false;
    }

    if (stackChars.empty())
        return true;
    else
        return false;

}

// Now there are not only parenthesis. There are also brackets [] and curly braces {}
// Cases
// )()
// ()(
// )()(
// The same as before for all (), [] and {}
// ({)}
// Run-time complexity O(n)
// Memory complexity O(n)
bool isCorrect(const string& sChars){

    stack<char> stackChars;

    for (char c : sChars){
        if (c == '(' || c == '[' || c == '{')
            stackChars.push(c);
        if (c == ')' || c == ']' || c == '}'){
            if (!stackChars.empty()){
                if (c == ')'){
                    if (stackChars.top() == '(')
                        stackChars.pop();
                    else
                        return false;
                }
                if (c == ']'){
                    if (stackChars.top() == '[')
                        stackChars.pop();
                    else
                        return false;
                }
                if (c == '}'){
                    if (stackChars.top() == '{')
                        stackChars.pop();
                    else
                        return false;
                }
            }
            else
                return false;
        }
    }

    if (stackChars.empty())
        return true;
    else
        return false;

}


// Run-time complexity O(n)
// Memory complexity O(n)
// Much cleaner like this
bool isOpener(char c) {
        return c=='(' || c=='[' || c=='{';
    }
    bool isCloser(char c) {
        return c==')' || c==']' || c=='}';
    }

    unordered_map<char, char> opposites = {
        {'(', ')'},
        {'[', ']'},
        {'{', '}'}
    };

    bool isValid(const string& s) {
        stack<char> stk;

        for (char c : s) {
            if (isOpener(c)) {
                stk.push(opposites[c]);
            }
            else if (isCloser(c)) {
                if (stk.empty() || stk.top() != c)
                    return false;
                stk.pop();
            }
        }

        return stk.empty();

    }


int main()
{
    string ex1 = "(())()()())()";
    bool sol1 = false;
    bool est1 = isCorrect(ex1);

    string ex2 = "(())()()(())()";
    bool sol2 = true;
    bool est2 = isCorrect(ex2);

    string ex3 = "(())()()(())(()";
    bool sol3 = false;
    bool est3 = isCorrect(ex1);

    string ex4 = "([])({})(){(())}()";
    bool sol4 = true;
    bool est4 = isCorrect(ex4);

    string ex5 = "([])({)}(){(())}()";
    bool sol5 = false;
    bool est5 = isCorrect(ex5);

    std::cout << "Solution Ex1: " << sol1 << std::endl;
    std::cout << "Estimation Ex1: " << est1 << std::endl;
    std::cout << "-----------------" << std::endl;
    std::cout << "Solution Ex2: " << sol2 << std::endl;
    std::cout << "Estimation Ex2: " << est2 << std::endl;
    std::cout << "-----------------" << std::endl;
    std::cout << "Solution Ex3: " << sol3 << std::endl;
    std::cout << "Estimation Ex3: " << est3 << std::endl;
    std::cout << "-----------------" << std::endl;
    std::cout << "Solution Ex4: " << sol4 << std::endl;
    std::cout << "Estimation Ex4: " << est4 << std::endl;
    std::cout << "-----------------" << std::endl;
    std::cout << "Solution Ex5: " << sol5 << std::endl;
    std::cout << "Estimation Ex5: " << est5 << std::endl;

    return 0;
}