// Prog: expression_OOP.cpp
// defines a class for expression trees,
// using different types of nodes

#include<iostream>
#include<cassert>
#include<cmath>
namespace ifmp
{
  // (abstract) base class for any xepression node
  // ---------------------------------------------
  struct xtree_node
  {
    // POST: evaluates the subtree with root *this
    virtual double eval () const = 0;

    // POST: the subtree with root *this is printed as
    //       fully parenthesized xepression
    virtual void print (std::ostream& o) const = 0;

    // POST: returns the size (number of nodes) in the
    //       subtree with root *this
    virtual int size () const = 0;

    // POST: a copy of the subtree with root *this is made,
    //       and a pointer to its root node is returned
    virtual xtree_node* copy () const = 0;

    // POST: all nodes in the subtree with
    // root *this are deleted, except *this itself
    virtual void clear () {};

    virtual ~xtree_node(){};
  };

  // class for leaf nodes with numbers (no children)
  // -----------------------------------------------
  struct number_node: public xtree_node
  {
    double val;

    // constructor
    number_node (double v)
    : val (v)
    {}

    double eval () const
    {
      return val;
    }

    void print (std::ostream& o) const
    {
      o << val;
    }

    int size () const
    {
      return 1;
    }

    xtree_node* copy () const
    {
      return new number_node (val);
    }
  };

  // class for leaf nodes with variables (no children)
  // -------------------------------------------------
  struct variable_node: public xtree_node
  {
    double* ptr;

    // constructor
    variable_node (double* p)
    : ptr (p)
    {}

    double eval () const
    {
      return *ptr;
    }

    void print (std::ostream& o) const
    {
      o << '[' << ptr << ']';
    }

    int size () const
    {
      return 1;
    }

    xtree_node* copy () const
    {
      return new variable_node (ptr);
    }
  };


  // (abstract) class for unary nodes (only a right child)
  // -----------------------------------------------------
  struct unary_node: public xtree_node
  {
    xtree_node* right; // INV != 0

    // constructor
    unary_node (xtree_node* r)
    : right (r)
    {
      assert (right);
    }

    int size () const
    {
      return 1 + right->size();
    }

    virtual void clear ()
    {
      right->clear();
      delete right;
    }

    // eval, print, copy defined in subclasses
  };

  // class for unary minus node
  // --------------------------
  struct minus_node: public unary_node
  {
    // constructor
    minus_node (xtree_node* r)
    : unary_node (r)
    {}

    double eval () const
    {
      return -right->eval();
    }

    void print (std::ostream& o) const
    {
      o << "-(";
      right->print(o);
      o << ')';
    }

    xtree_node* copy () const
    {
      return new minus_node (right->copy());
    }
  };

  // (abstract) class for binary nodes (left and right child)
  // --------------------------------------------------------
  struct binary_node: public xtree_node
  {
    xtree_node* left; // INV != 0
    xtree_node* right; // INV != 0

    // constructor
    binary_node (xtree_node* l, xtree_node* r)
      : left (l), right (r)
    {
      assert (left);
      assert (right);
    }

    int size () const
    {
      return 1 + left->size() + right->size();
    }

    virtual void clear ()
    {
      left->clear(); delete left;
      right->clear();delete right;
    }

    // eval, print, copy defined in subclasses
  };

  // class for binary + nodes
  // ------------------------
  struct add_node : public binary_node
  {
    // constructor
    add_node (xtree_node* l, xtree_node* r)
      : binary_node (l, r)
    {}

    double eval () const
    {
      return left->eval() + right->eval();
    }

    void print (std::ostream& o) const
    {
      o << '(';
      left->print(o);
      o << '+';
      right->print(o);
      o << ')';
    }

    xtree_node* copy () const
    {
      return new add_node (left->copy(), right->copy());
    }
  };

  // class for binary - nodes
  // ------------------------
  struct sub_node : public binary_node
  {
    // constructor
    sub_node (xtree_node* l, xtree_node* r)
      : binary_node (l, r)
    {}

    double eval () const
    {
      return left->eval() - right->eval();
    }

    void print (std::ostream& o) const
    {
      o << '(';
      left->print(o);
      o << '-';
      right->print(o);
      o << ')';
    }

    xtree_node* copy () const
    {
      return new sub_node (left->copy(), right->copy());
    }
  };

  // class for binary * nodes
  // ------------------------
  struct mul_node : public binary_node
  {
    // constructor
    mul_node (xtree_node* l, xtree_node* r)
      : binary_node (l, r)
    {}

    double eval () const
    {
      return left->eval() * right->eval();
    }

    void print (std::ostream& o) const
    {
      o << '(';
      left->print(o);
      o << '*';
      right->print(o);
      o << ')';
    }

    xtree_node* copy () const
    {
      return new mul_node (left->copy(), right->copy());
    }
  };

  // class for binary / nodes
  // ------------------------
  struct div_node : public binary_node
  {
    // constructor
    div_node (xtree_node* l, xtree_node* r)
      : binary_node (l, r)
    {}

    double eval () const
    {
      return left->eval() / right->eval();
    }

    void print (std::ostream& o) const
    {
      o << '(';
      left->print(o);
      o << '/';
      right->print(o);
      o << ')';
    }

    xtree_node* copy () const
    {
      return new div_node (left->copy(), right->copy());
    }
  };

  // class for abs nodes
  // -------------------
  struct abs_node: public unary_node
  {
    // constructor
    abs_node (xtree_node* arg)
    : unary_node (arg)
    {}

    double eval () const
    {
      return std::abs (right->eval());
    }

    void print (std::ostream& o) const
    {
      // internal node
      o << "abs" << '(';
      right->print(o);
      o << ')';
    }

    xtree_node* copy () const
    {
      return new abs_node (right->copy());
    }
  };

  class xepression
  {
  private:
    xtree_node* root;

    // POST: the size (number of nodes) of *this is returned
    int size(xtree_node* n) const
    {
      if (n) return n->size();
      return 0;
    }

  public:

    // POST: *this is an empty xepression
    xepression ()
      : root (0)
    {}

    // POST: *this has one node with value d
    xepression (double d)
    : root (new number_node (d))
    {}

    // POST: *this has one node whose value found
    //       at address ptr
    xepression (double* ptr)
    : root (new variable_node (ptr))
    {}

    // copy constructor
    xepression (const xepression& v)
    : root (0)
    {
      root = v.root->copy();
    }

    // assignment operator
    xepression& operator= (const xepression& v)
    {
      if (root != v.root)   // avoid self-assignment
        {
	  delete root;
	  root = 0;
	  if (v.root) root = v.root->copy();
        }
      return *this;
    }

    // += operator
    xepression& operator+= (const xepression& t)
    {
      assert(t.root);
      root = new add_node (root, t.root->copy());
      return *this;
    }

    // -= operator
    xepression& operator-= (const xepression& t)
    {
      assert(t.root);
      root = new sub_node (root, t.root->copy());
      return *this;
    }

    // *= operator
    xepression& operator*= (const xepression& t)
    {
      assert(t.root);
      root = new mul_node (root, t.root->copy());
      return *this;
    }

    // /= operator
    xepression& operator/= (const xepression& t)
    {
      assert(t.root);
      root = new div_node (root, t.root->copy());
      return *this;
    }

    // replaces *this with abs (*this)
    xepression& abs()
    {
      root = new abs_node(root->copy());
      return *this;
    }

    // replaces *this with -(*this)
    xepression& negate()
    {
      root = new minus_node(root->copy());
      return *this;
    }

    // destructor
    ~xepression ()
    {
      if (root) {
	root->clear();
	delete root;
      }
    }

    // POST: evaluates *this
    double evaluate () const
    {
      if (root) return root->eval();
      return 0;
    }

    // POST: *this is printed as fully
    //       parenthesized xepression
    void print (std::ostream& o) const
    {
      if (root) root->print (o);
    }

    // POST: the size (number of nodes) of *this is returned
    int size() const
    {
      if (root) return root->size();
      return 0;
    }

  };

  // POST: l + r is returned
  xepression operator+ (const xepression& l, const xepression& r)
  {
    xepression result = l;
    return result += r;
  }

  // POST: l - r is returned
  xepression operator- (const xepression& l, const xepression& r)
  {
    xepression result = l;
    return result -= r;
  }

  // POST: l * r is returned
  xepression operator* (const xepression& l, const xepression& r)
  {
    xepression result = l;
    return result *= r;
  }

  // POST: l / r is returned
  xepression operator/ (const xepression& l, const xepression& r)
  {
    xepression result = l;
    return result /= r;
  }

  // POST: -r is returned
  xepression operator- (const xepression &r)
  {
    xepression result = r;
    return result.negate();
  }

  // POST: abs (r) is returned
  xepression abs (const xepression &r)
  {
    xepression result = r;
    return result.abs();
  }

  // POST: *this is written to o
  std::ostream& operator<< (std::ostream& o, const xepression& v)
  {
    v.print(o);
    return o;
  }

} // end namespace ifmp