// Prog: expression.cpp
// defines a class for expression trees
#include<iostream>
#include<cassert>

namespace ifmp
{
  // texpression tree node
  struct tree_node
  {
    char op;

    // internal node ( op: '+, '-', '*', '/')
    tree_node* left;
    tree_node* right;

    // leaf node (op: '=')
    double val;

    // constructor
    tree_node (char o, tree_node* l, tree_node* r, double v)
      : op (o), left (l), right (r), val (v)
    {}

    // POST: all nodes in the subtree with 
    // root *this are deleted, except *this itself
    void clear()
    {
      if (left) {
	left->clear();
	delete left;
      }
      if (right){
	right->clear();
	delete right;
      }
    }

    // POST: evaluates the subtree with root *this
    double eval () const
    {
      if (op == '=') return val;
      double l = 0;
      if (left != 0) l = left->eval();
      double r = right->eval();
      if (op == '+') return l + r;
      if (op == '-') return l - r;
      if (op == '*') return l * r;
      if (op == '/') return l / r;
      assert (false); // unknown operator
      return 0;
    }

    // POST: the subtree with root *this is printed as fully
    //       parenthesized texpression
    void print (std::ostream& o) const
    {
      if (op == '=')
	// leaf
	o << val;
      else
        {
	  // internal node
	  o << '(';
	  if (left)
	    left->print(o);
	  o << op;
	  assert(right);
	  right->print(o);
	  o << ')';
        }
    }

    // POST: returns the size (number of nodes) of the
    //       subtree with root *this
    int size () const
    {
      int s=1;
      if (left) s += left->size();
      if (right) s += right->size();
      return s;
    }

    // POST: a copy of the subtree with root *this is made,
    //       and a pointer to its root node is returned
    tree_node* copy () const
    {
      tree_node* to = new tree_node (op, 0, 0, val);
      if (left) to->left = left->copy();
      if (right) to->right = right->copy();
      return to;
    }
  };

  class texpression
  {
  private:
    tree_node* root;

    // POST: a copy of the tree starting with n
    //       is returned if any, null otherwise
    tree_node* copy(const tree_node* n)
    {
      if (n) return n->copy();
      return 0;
    }

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

    // POST: prints one row during prettyprinting
    void print_row (std::ostream& o, double row) const
    {
      char last = 'x';
      const tree_node* n = root;
      while (n != 0)
        {
	  if (row < size (n->right))
            {
	      if (last == 'l')
		o << "|   ";
	      else
		o << "    ";
	      last = 'r';
	      n = n->right;
	      continue;
            }
	  if (row > size (n-> right))
            {
	      if (last == 'r')
		o << "|   ";
	      else
		o << "    ";
	      last = 'l';
	      row = row - size(n->right) - 1;
	      n = n->left;
	      continue;
            }
	  assert (row == size (n->right));
	  if (n->op == '=')
	    o << " --(" << n->val << ")";
	  else
	    o << " --(" << n->op << ")";
	  break;
        }
    }


  public:

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

    // POST: *this has one node with value d
    texpression (double d)
    : root (new tree_node ('=', 0, 0, d))
    {}

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

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

    // negation
    texpression& negate ()
    {
      root = new tree_node ('-', 0, root, 0);
      return *this;
    }

    // += operator
    texpression& operator+= (const texpression& t)
    {
      assert(t.root);
      root = new tree_node ('+', root, t.root->copy(),0);
      return *this;
    }

    // -= operator
    texpression& operator-= (const texpression& t)
    {
      assert(t.root);
      root = new tree_node ('-', root, t.root->copy(),0);
      return *this;
    }

    // *= operator
    texpression& operator*= (const texpression& t)
    {
      assert(t.root);
      root = new tree_node ('*', root, t.root->copy(),0);
      return *this;
    }

    // /= operator
    texpression& operator/= (const texpression& t)
    {
      assert(t.root);
      root = new tree_node ('/', root, t.root->copy(),0);
      return *this;
    }

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

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

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

    // POST: *this is printed to o as a tree
    void pretty_print (std::ostream& o) const
    {
      for (double row = 0; row < size(); row+=0.5)
        {
	  print_row (o, row);
	  o << std::endl;
        }
    }

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

  };

  // POST: the negative of t is returned
  texpression operator- (const texpression& t)
  {
    texpression result = t;
    return result.negate();
  }

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

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

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

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

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

} // end namespace ifmp