#include <stack>
#include <string>
#include <iostream>
#include <array>
#include <iomanip>
#include <utility>

std::string quote(std::string s)
{
    return '"' + s + '"';
}

template <typename T>
T pop_top(std::stack<T>& stack)
{
    T result = stack.top();
    stack.pop();
    return result;
}

// returns a bool/index pair.  If .first is true, then the parens balance, and .second
// should be ignored.  If .first is false, then the parens don't balance, and .second
// is the "index" where the offending paren was found, or if more parens were required
// it is one past the end.
std::pair<bool, std::size_t> parens_balance(const std::string& s)
{
    unsigned left_paren_count = 0;
    unsigned right_paren_count = 0;
    // char expression = 'a' ;

    std::stack<char> stack;

    auto ss = s.begin();
    while (ss != s.end())
    {
        char ch = *ss++;

        if (ch == '(')
        {
            stack.push(ch);
            // stack.push(expression++);

            ++left_paren_count;
        }
        else if (ch == ')')
        {
            if (++right_paren_count > left_paren_count || stack.empty())
                return std::make_pair(false, ss - s.begin() - 1);

            // auto indent_level = left_paren_count - right_paren_count;

            while (!stack.empty() && (ch = pop_top(stack)) != '(')
                /*std::cout << std::string(indent_level, ' ') << ch << '\n'*/;
        }
    }

    std::size_t index = s.size();
    if (stack.empty() && left_paren_count < right_paren_count)
        --index;

    return std::make_pair(stack.empty() && left_paren_count == right_paren_count, index);
}

void report_unbalanced_parens(const std::string& expr, std::size_t index)
{
    std::cout << "Unbalanced parentheses detected in " << quote(expr) << ":\n\t";
    std::cout << expr << "\n\t";
    std::cout << std::string(index, ' ') << "^\n";
}

int main()
{
    std::array<std::string, 10> expressions = 
    { 
        "(()(()))()(()",        // invalid
        "(()(()))()(())",       // valid
        "()",                   // valid
        ")",                    // invalid
        "(",                    // invalid
        "()()()",               // valid
        "(((()))((())))",       // valid
        "))((",                 // invalid
        "())(",                 // invalid
        "(()(",                 // invalid
    };

    for (auto& expression : expressions)
    {
        auto ret = parens_balance(expression);
        if (ret.first)
            std::cout << quote(expression) << " has balanced parentheses.\n";
        else
            report_unbalanced_parens(expression, ret.second);

        std::cout << '\n';
    }
}