C++11 template for math expressions

expression.hh

#ifndef EXPRESSION_HH__
#define EXPRESSION_HH__

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

namespace reasoning {

// Forward declarations:
template<typename NUM, typename VAR> struct add;
template<typename NUM, typename VAR> struct multiply;

/**
  \brief Generic type for math expressions with a type for numbers (NUM) and
  one for variables (VAR).

  \tparam NUM Type for numbers.
  \tparam VAR Type for variables.
 */
template<typename NUM = int, typename VAR = std::string>
using expression = boost::variant<
  NUM,
  VAR,
  boost::recursive_wrapper<add<NUM, VAR>>,
  boost::recursive_wrapper<multiply<NUM, VAR>>>;

/**
  \brief Base class for binary operations (adding, multiplying...).
 */
template<typename NUM, typename VAR>
class binary_op {
  expression<NUM, VAR> m_left, m_right;
public:
  /** \brief Builds a binary operation with a left and right expressions. */
  binary_op(expression<NUM, VAR> const& left,
            expression<NUM, VAR> const& right)
            noexcept : m_left(left), m_right(right) {
  }

  /**
    \brief Returns the left side of the expression.
   */
  auto left() const -> expression<NUM, VAR> const& { return m_left; }

  /**
    \brief Returns the right side of the expression
    (no, seriously, what did you expect?).
   */
  auto right() const -> expression<NUM, VAR> const& { return m_right; }
};

template<typename NUM, typename VAR>
struct add : public binary_op<NUM, VAR> {
  add(expression<NUM, VAR> const& left,
      expression<NUM, VAR> const& right)
      noexcept : binary_op<NUM, VAR>(left, right) {
  }
};

template<typename NUM, typename VAR>
struct multiply : public binary_op<NUM, VAR> {
  multiply(expression<NUM, VAR> const& left,
           expression<NUM, VAR> const& right)
           noexcept : binary_op<NUM, VAR>(left, right) {
  }
};

template<typename NUM, typename VAR>
struct add_visit : public boost::static_visitor<expression<NUM, VAR>> {
  auto operator()(NUM x, NUM y) const -> expression<NUM, VAR> {
    return x + y;
  }

  template<typename Y>
  auto operator()(NUM x, Y const& y) const -> expression<NUM, VAR> {
    return x == 0? expression<NUM, VAR>(y) : add<NUM, VAR>(x, y);
  }

  template<typename X>
  auto operator()(X const& x, NUM y) const -> expression<NUM, VAR> {
    return y == 0? expression<NUM, VAR>(x) : add<NUM, VAR>(x, y);
  }

  template<typename X, typename Y>
  auto operator()(X const& x, Y const& y) const -> expression<NUM, VAR> {
    return add<NUM, VAR>(x, y);
  }
};

template<typename NUM, typename VAR>
struct multiply_visit : public boost::static_visitor<expression<NUM, VAR>> {
  auto operator()(NUM x, NUM y) const -> expression<NUM, VAR> {
    return x * y;
  }

  template<typename Y>
  auto operator()(NUM x, Y const& y) const -> expression<NUM, VAR> {
    if (x == NUM{0})
      return 0;
    if (x == NUM{1})
      return y;
    return multiply<NUM, VAR>{x, y};
  }

  template<typename X>
  auto operator()(X const& x, NUM y) const -> expression<NUM, VAR> {
    // return this(y, x);
    if (y == NUM{0})
      return 0;
    if (y == NUM{1})
      return x;
    return multiply<NUM, VAR>{x, y};
  }

  template<typename X, typename Y>
  auto operator()(X const& x, Y const& y) const -> expression<NUM, VAR> {
    return multiply<NUM, VAR>{x, y};
  }
};

template<typename NUM, typename VAR>
struct simplify1 : public boost::static_visitor<expression<NUM, VAR>> {
  auto operator()(add<NUM, VAR> const& a) const -> expression<NUM, VAR> {
    return boost::apply_visitor(add_visit<NUM, VAR>(), a.left(), a.right());
  }

  auto operator()(multiply<NUM, VAR> const& m) const -> expression<NUM, VAR> {
    return boost::apply_visitor(multiply_visit<NUM, VAR>(), m.left(), m.right());
  }

  template<typename X>
  auto operator()(X const& x) const -> expression<NUM, VAR> {
    return x;
  }
};

template<typename NUM, typename VAR>
struct simplify : public boost::static_visitor<expression<NUM, VAR>> {
  template<typename X>
  auto simplification(X const& x) const -> expression<NUM, VAR> {
    return boost::apply_visitor(simplify<NUM, VAR>(), x);
  }

  auto operator()(add<NUM, VAR> const& a) const -> expression<NUM, VAR> {
    auto const left = simplification(a.left()), right = simplification(a.right());
    auto const add_lr = boost::apply_visitor(add_visit<NUM, VAR>(), left, right);
    return boost::apply_visitor(simplify1<NUM, VAR>(), add_lr);
  }

  auto operator()(multiply<NUM, VAR> const& m) const -> expression<NUM, VAR> {
    auto const left = simplification(m.left()), right = simplification(m.right());
    auto const mul_lr = boost::apply_visitor(multiply_visit<NUM, VAR>(), left, right);
    return boost::apply_visitor(simplify1<NUM, VAR>(), mul_lr);
  }

  template<typename X>
  auto operator()(X const& x) const -> expression<NUM, VAR> {
    return x;
  }
};

/**
  \brief Visitor used to format expression.
 */
template<typename NUM, typename VAR>
class visit_fmt_expr : public boost::static_visitor<std::string> {
  // Used do determine when to add parentheses.
  size_t m_parens;

  // Surround string if true, doesn't do shit otherwise.
  auto surround_if(bool b, std::string const& s) const -> std::string {
    return b ? "(" + s + ")" : s;
  }

  // Format for infix operators.
  auto show_infix(bool b, size_t pr, std::string const& sym,
                  expression<NUM, VAR> const& x, expression<NUM, VAR> const& y)
                  const -> std::string {
    auto const left = boost::apply_visitor(visit_fmt_expr<NUM, VAR>(pr + 1), x);
    auto const right = boost::apply_visitor(visit_fmt_expr<NUM, VAR>(pr), y);
    return surround_if(b, left + " " + sym + " " + right);
  }

public:
  visit_fmt_expr(size_t parens = 0) : m_parens(parens) {
  }

  auto operator()(add<NUM, VAR> const& a) const -> std::string {
    return show_infix((m_parens > 2), 1, " + ", a.left(), a.right());
  }

  auto operator()(multiply<NUM, VAR> const& m) const -> std::string {
    return show_infix((m_parens > 4), 3, " * ", m.left(), m.right());
  }

  template<typename T>
  auto operator()(T const& t) const -> std::string {
    return boost::lexical_cast<std::string>(t);
  }
};

// Operators

// Overload to simplify building additions.
template<typename NUM, typename VAR>
auto operator+(expression<NUM, VAR> const& x,
               expression<NUM, VAR> const& y) -> expression<NUM, VAR> {
  return add<NUM, VAR>(x, y);
}

// Overload to simplify building multiplications.
template<typename NUM, typename VAR>
auto operator*(expression<NUM, VAR> const& x,
               expression<NUM, VAR> const& y) -> expression<NUM, VAR> {
  return multiply<NUM, VAR>(x, y);
}

template<typename NUM, typename VAR>
auto operator<<(std::ostream &oss, expression<NUM, VAR> const& expr)
                -> std::ostream& {
  oss << boost::apply_visitor(visit_fmt_expr<NUM, VAR>(), expr);
  return oss;
}

// For == to work, this operator needs to be defined for all possible variants.
template<typename NUM, typename VAR>
auto operator==(binary_op<NUM, VAR> const& x, binary_op<NUM, VAR> const& y)
                -> bool {
  return x.left() == y.left() && x.right() == y.right();
}

// For some reason, != is not supported directly by boost::variant, but it's
// trivial to define from ==.

template<typename NUM, typename VAR>
auto operator!=(expression<NUM, VAR> const& x, expression<NUM, VAR> const& y)
                -> bool {
  return !(x == y);
}

} /* end namespace reasoning */

#endif