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

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

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

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

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

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

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

    // 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
    {
      return new tree_node (op, val,
			    left ? left->copy() : 0,
			    right ? right->copy() : 0);
    }
  };

  class texpression
  {
  private:
    tree_node* root;

  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 ('=', d, 0, 0))
    {}

    // copy constructor
    texpression (const texpression& v)
      : root (v.root ? v.root->copy() : 0)
    {}

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

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

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

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

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

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

    // POST: evaluates the subtree with root *this
    double evaluate () const
    {
      return root ? root->eval() : 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
    {
      if (root) {
	for (double row = 0; row < root->size(); row+=0.5) {
	  root->print_row (o, row);
	  o << std::endl;
        }
      }
    }
  };

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

  // 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