#include <cctype>
#include <iostream>
#include <memory>
#include <sstream>
#include <vector>

class node
{
public:
    virtual ~node() = default;
    virtual void evaluate(std::ostream& output) const = 0;
};

using node_ptr = std::unique_ptr<node>;
using node_sequence = std::vector<node_ptr>;

class literal : public node
{
public:
    explicit literal(char symbol) : symbol_(symbol) {}

    void evaluate(std::ostream& output) const override
    {
        output.put(symbol_);
    }

private:
    char symbol_;
};

class repetition : public node
{
public:
    explicit repetition(size_t count) : count_(count)
    {
        if (count < 1) {
            throw std::runtime_error("Invalid repetition count");
        }
    }

    void evaluate(std::ostream& output) const override
    {
        for (size_t i(0); i < count_; ++i) {
            for (auto const& child : children) {
                child->evaluate(output);
            }
        }
    }

    node_sequence children;
private:
    size_t count_;
};

size_t parse_count(std::istream& input)
{
    size_t count(0);

    while (input) {
        int const next_symbol = input.peek();
        if (std::isdigit(next_symbol)) {
            count = count * 10 + (input.get() - '0');
        } else {
            break;
        }
    }

    return count;
}

void parse_required_symbol(std::istream& input, char c)
{
    if (input.peek() == EOF) {
        throw std::runtime_error("Unexpected end if input.");
    }
    if (input.get() != c) {
        throw std::runtime_error("Unexpected input symbol.");
    }
}

void parse_sequence(std::istream& input, node_sequence& children);

std::unique_ptr<literal> parse_literal(std::istream& input)
{
    return std::make_unique<literal>(input.get());
}

std::unique_ptr<repetition> parse_repetition(std::istream& input)
{
    // First the repetition count
    size_t const count = parse_count(input);

    // Now we expect an opening paren
    parse_required_symbol(input, '(');

    auto repeat_node = std::make_unique<repetition>(count);
    parse_sequence(input, repeat_node->children);

    // Now we expect a closing paren
    parse_required_symbol(input, ')');

    return repeat_node;
}

void parse_sequence(std::istream& input, node_sequence& children)
{
    while (input) {
        char const next_symbol = input.peek();
        if (std::isalpha(next_symbol)) {
            children.push_back(parse_literal(input));
        } else if (std::isdigit(next_symbol) && (next_symbol != '0')) {
            children.push_back(parse_repetition(input));
        } else {
            break;
        }
    }
}

node_ptr parse_stream(std::istream& input)
{
    auto root_node = std::make_unique<repetition>(1);

    parse_sequence(input, root_node->children);

    if (input.peek() != EOF) {
        std::string remainder(std::istreambuf_iterator<char>(input), {});
        throw std::runtime_error("Incomplete parse (remainder='" + remainder + "').");
    }

    return root_node;
}

std::string decompress(std::string compressed)
{
    std::stringstream input(compressed);

    node_ptr ast = parse_stream(input);

    std::stringstream output;
    ast->evaluate(output);

    return output.str();
}

int main()
{
    std::vector<std::string> test_strings = {
        "ABCD"
        , "AB2(CD)"
        , "2(AB3(CD))EF"
        , "AB(CD"
        , "AB2(CD"
        , "AB2(CD))"
    };

    for (auto const& test_string : test_strings) {
        std::cout << "Input = '" << test_string << "'\n";
        try {
            auto const decompressed = decompress(test_string);
            std::cout << "Output = '" << decompressed << "'\n";
        } catch (std::runtime_error& e) {
            std::cout << "Error: " << e.what() << '\n';
        }
    }

    return 0;
}