/*
 *  test for Boost.Variant
 *
 *  This sample needs recursive evaluations to execute, therefore there is a
 *  stack overflow risk.
 *
 *  written by janus_wel<janus.wel.3@gmail.com>
 *  This source code is in public domain, and has NO WARRANTY.
 * */

#include <iostream>
#include <boost/variant.hpp>

namespace four_arithmetic_ops {
    // definitions of four arithmetic operations
    struct add { static char symbol(void) { return '+'; } };
    struct sub { static char symbol(void) { return '-'; } };
    struct mul { static char symbol(void) { return '*'; } };
    struct div { static char symbol(void) { return '/'; } };

    // definitions of data structure
    // syntax tree by using binary tree
    template <typename Op> struct binary_op;

    typedef boost::variant<
        double,
        boost::recursive_wrapper<binary_op<add> >,
        boost::recursive_wrapper<binary_op<sub> >,
        boost::recursive_wrapper<binary_op<mul> >,
        boost::recursive_wrapper<binary_op<div> >
            > expr;

    template <typename Op>
    struct binary_op {
        expr left;
        expr right;

        binary_op(const expr& lhs, const expr& rhs)
            : left(lhs), right(rhs) {}
    };

    // for convenience
    typedef binary_op<add> op_add;
    typedef binary_op<sub> op_sub;
    typedef binary_op<mul> op_mul;
    typedef binary_op<div> op_div;

    // evaluate data structure recursively
    struct evaluator : public boost::static_visitor<double> {
        double operator()(const double& value) const {
            return value;
        }

        double operator()(const op_add& i) const {
            return
                  boost::apply_visitor(evaluator(), i.left)
                + boost::apply_visitor(evaluator(), i.right);
        }

        double operator()(const op_sub& i) const {
            return
                  boost::apply_visitor(evaluator(), i.left)
                - boost::apply_visitor(evaluator(), i.right);
        }

        double operator()(const op_mul& i) const {
            return
                  boost::apply_visitor(evaluator(), i.left)
                * boost::apply_visitor(evaluator(), i.right);
        }

        double operator()(const op_div& i) const {
            return
                  boost::apply_visitor(evaluator(), i.left)
                / boost::apply_visitor(evaluator(), i.right);
        }
    };

    // for print
    template<typename Op>
    std::ostream& operator<<(std::ostream& out, const binary_op<Op>& b) {
        return out
            << '(' << b.left << ' '
            << Op::symbol()
            << ' ' << b.right << ')';
    }

    // for convenience
    inline double calc(const expr& e) {
        return boost::apply_visitor(evaluator(), e);
    }

    // for convenience, but these are over the top...
    op_add operator+(const expr& a, const expr& b) {
        return op_add(a, b);
    }
    op_sub operator-(const expr& a, const expr& b) {
        return op_sub(a, b);
    }
    op_mul operator*(const expr& a, const expr& b) {
        return op_mul(a, b);
    }
    op_div operator/(const expr& a, const expr& b) {
        return op_div(a, b);
    }
}

int main(void) {
    using namespace four_arithmetic_ops;

    /*
     *  This is equivalent to below expressions
     *      expr e((expr(9) / expr(3)) * (expr(7) - expr(2)) + expr(8));
     * */
    expr e(
            op_add(
                op_mul(
                    op_div(9, 3),
                    op_sub(7, 2)),
                8));
    std::cout
        << e << " = " << calc(e)
        << std::endl;
    return 0;
}