#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;

}

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;
}