#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <ctime>
#include <memory>
#include <boost/rational.hpp>
#include <boost/shared_ptr.hpp>

bool is_valid_rpn_form(const std::vector<bool> &s){
    int n = 0;
    for (const auto &c : s){
        if (!c)
            n++;
        else
            n--;
        if (n < 1)
            return 0;
    }
    return n == 1;
}

std::vector<std::vector<bool> > generate_all_partial_expressions(unsigned operands){
    std::vector<std::vector<bool> > ret;
    std::vector<bool> s;
    if (!operands){
        ret.push_back(s);
        return ret;
    }
    s.push_back(0);
    if (operands == 1){
        ret.push_back(s);
        return ret;
    }
    s.push_back(0);
    unsigned operators = operands - 1;
    operands -= 2;
    for (unsigned i = 0; i < operands; i++)
        s.push_back(0);
    for (unsigned i = 0; i < operators; i++)
        s.push_back(1);
    ret.push_back(s);
    while (std::next_permutation(s.begin() + 2, s.end())){
        if (!is_valid_rpn_form(s))
            continue;
        ret.push_back(s);
    }
    return ret;
}

enum class Operation{
    ADD = 0,
    SUB = 1,
    MUL = 2,
    DIV = 3,
};

#if 1
typedef boost::rational<int> main_type;
#elif 0
typedef double main_type;
#else
typedef int main_type;
#endif

struct sol_t{
    bool is_number;
    main_type value;
};

const unsigned OPERAND_COUNT = 6;

class Searcher{
    std::vector<std::vector<std::vector<bool> > > expression_trees;
    main_type operands[OPERAND_COUNT];
    main_type result;

    void level0(){
        //Search possible operand combinations.
        auto m = OPERAND_COUNT;
        const unsigned n = 1 << m;
        for (unsigned i = 1; i < n; i++){
            std::vector<main_type> current_operands;
            {
                unsigned copy_i = i;
                for (unsigned j = 0; j < m; j++, copy_i >>= 1)
                    if (copy_i & 1)
                        current_operands.push_back(this->operands[j]);
            }
            std::sort(current_operands.begin(), current_operands.end());
            this->level1(current_operands);
        }
    }
    void level1(std::vector<main_type> &current_operands){
        const unsigned n = 1 << ((current_operands.size() - 1) * 2);
        //Search multiple operator orders.
        for (unsigned operator_order = 0; operator_order < n; operator_order++)
            this->level2(current_operands, operator_order);
    }
    void level2(std::vector<main_type> &current_operands, unsigned operator_order){
        //Search multiple operand orders.
        auto it = current_operands.begin();
        auto end = it + current_operands.size();
        while (std::next_permutation(it, end))
            this->level3(current_operands, operator_order);
    }
    void level3(const std::vector<main_type> &current_operands, unsigned operator_order){
        auto &possible_expression_trees = this->expression_trees[current_operands.size()];
        for (auto &expr : possible_expression_trees)
            this->evaluate(current_operands, operator_order, expr);
    }
    void evaluate(const std::vector<main_type> &current_operands, unsigned operator_order, const std::vector<bool> &current_expression);
public:
    std::vector<sol_t> all_solutions;
    Searcher(const int operands[OPERAND_COUNT], int result): result(result){
        std::copy(operands, operands + OPERAND_COUNT, this->operands);
        std::sort(this->operands, this->operands + 5);
        for (unsigned i = 0; i <= OPERAND_COUNT; i++){
            auto exprs = generate_all_partial_expressions(i);
            this->expression_trees.push_back(exprs);
        }
    }
    void search(){
        this->level0();
    }
};

void Searcher::evaluate(const std::vector<main_type> &current_operands, unsigned operator_order, const std::vector<bool> &current_expression){
    unsigned operators = operator_order;
    sol_t solution[OPERAND_COUNT * 2 - 1];
    int solution_size = 0;
    main_type stack[6];
    int stack_end = -1;
    int n = 0;
    for (const auto &op : current_expression){
        if (!op){
            auto operand = current_operands[n++];
            solution[solution_size].is_number = 1;
            solution[solution_size].value = operand;
            solution_size++;
            stack[++stack_end] = operand;
        }else{
            unsigned op = operators & 3;
            operators >>= 2;

            solution[solution_size].is_number = 0;
            solution[solution_size].value = op + 1;
            solution_size++;

            auto operand = stack[stack_end--];
            auto &operand2 = stack[stack_end];
            switch ((Operation)op){
                case Operation::ADD:
                    operand2 += operand;
                    break;
                case Operation::SUB:
                    operand2 -= operand;
                    break;
                case Operation::MUL:
                    operand2 *= operand;
                    break;
                case Operation::DIV:
                    if (!operand)
                        return;
                    operand2 /= operand;
                    break;
            }
        }
    }
    if (stack[stack_end] != this->result)
        return;
    for (int i = 0; i < solution_size; i++)
        this->all_solutions.push_back(solution[i]);
    sol_t temp = { 0, 0 };
    this->all_solutions.push_back(temp);
}

int to_int(int x){
    return x;
}

int to_int(float x){
    return (int)x;
}

int to_int(double x){
    return (int)x;
}

int to_int(const boost::rational<int> &x){
    return x.numerator();
}

class TreeElement{
public:
    virtual ~TreeElement(){}
    virtual main_type get_value() = 0;
    virtual void output(std::vector<sol_t> &) = 0;
    virtual void output(std::ostream &) = 0;
    virtual void output_rpn(std::ostream &) = 0;
    virtual unsigned get_precedence() = 0;
    virtual bool is_constant() const{
        return 0;
    }
};

class NumberTreeElement : public TreeElement{
public:
    int value;
    NumberTreeElement(int value): value(value){}
    main_type get_value(){
        return this->value;
    }
    void output(std::vector<sol_t> &dst){
        sol_t temp = {
            1,
            this->value,
        };
        dst.push_back(temp);
    }
    void output(std::ostream &stream){
        stream <<value;
    }
    void output_rpn(std::ostream &stream){
        this->output(stream);
    }
    unsigned get_precedence(){
        return UINT_MAX;
    }
    bool is_constant() const{
        return 1;
    }
};

class OperatorTreeElement : public TreeElement{
    bool computed;
    main_type value;
    typedef boost::shared_ptr<TreeElement> op_t;
public:
    Operation op;
    op_t left,
        right;
    OperatorTreeElement(Operation op, boost::shared_ptr<TreeElement> left, boost::shared_ptr<TreeElement> right): op(op), left(left), right(right), computed(0){}
    main_type get_value(){
        if (!this->computed){
            switch (this->op){
                case Operation::ADD:
                    this->value = this->left->get_value() + this->right->get_value();
                    break;
                case Operation::SUB:
                    this->value = this->left->get_value() - this->right->get_value();
                    break;
                case Operation::MUL:
                    this->value = this->left->get_value() * this->right->get_value();
                    break;
                case Operation::DIV:
                    this->value = this->left->get_value() / this->right->get_value();
                    break;
            }
            this->computed = 1;
        }
        return this->value;
    }
    void output(std::vector<sol_t> &dst){
        this->left->output(dst);
        this->right->output(dst);
        sol_t temp = {
            0,
            (int)this->op + 1,
        };
        dst.push_back(temp);
    }
    void output(std::ostream &stream){
        bool l = this->left->get_precedence() < this->get_precedence();
        bool r = this->right->get_precedence() < this->get_precedence() || ((int)this->op % 2 && !this->right->is_constant());
        if (l)
            stream <<'(';
        this->left->output(stream);
        if (l)
            stream <<')';
        static const char char_operators[] = "+-*/";
        stream <<' '<<char_operators[(int)this->op]<<' ';
        if (r)
            stream <<'(';
        this->right->output(stream);
        if (r)
            stream <<')';
    }
    void output_rpn(std::ostream &stream){
        this->left->output_rpn(stream);
        stream <<' ';
        this->right->output_rpn(stream);
        static const char char_operators[] = "+-*/";
        stream <<' '<<char_operators[(int)this->op];
    }
    unsigned get_precedence(){
        return (unsigned)this->op / 2;
    }
};

boost::shared_ptr<TreeElement> build_tree(sol_t *&list){
    boost::shared_ptr<TreeElement> stack[OPERAND_COUNT * 2 - 1];
    int stack_end = -1;
    while (1){
        if (list->is_number){
            stack[++stack_end].reset(new NumberTreeElement(to_int(list->value)));
        }else{
            if (!to_int(list->value)){
                list++;
                return stack[stack_end];
            }

            auto operand2 = stack[stack_end--];
            auto operand = stack[stack_end--];
            auto op = (Operation)(to_int(list->value) - 1);
            stack[++stack_end].reset(new OperatorTreeElement(op, operand, operand2));
        }
        list++;
    }
}

int main(){
    int operands[] = { 3, 7, 8, 10, 50, 100 };
    Searcher searcher(operands, 315);
    auto t0 = clock();
    searcher.search();
    auto t1 = clock();
    {
        std::ofstream rpn_file("rpn.txt");
        std::ofstream infix_file("infix.txt");
        for (auto p = &searcher.all_solutions[0]; p < &searcher.all_solutions.back() + 1;){
            auto p2 = build_tree(p);
            p2->output_rpn(rpn_file);
            p2->output(infix_file);
            rpn_file <<std::endl;
            infix_file <<std::endl;
        }
    }
    std::cout <<"Done in "<<double(t1 - t0)/double(CLOCKS_PER_SEC)<<std::endl;

    return 0;
}