//--------------------------------------------------------------------
//
//  Laboratory 11                                           exprtree.C
//
//  SOLUTION: Linked implementation of the Expression Tree ADT
//
//--------------------------------------------------------------------

#include <iostream.h>
#include <assert.h>
#include <ctype.h>
#include "exprtree.h"

//--------------------------------------------------------------------

ExprTreeNode:: ExprTreeNode ( char elem,
                              ExprTreeNode *leftPtr,
                              ExprTreeNode *rightPtr )

// Creates an expreesion tree node containing element elem, left child
// pointer leftPtr, and right child pointer rightPtr.

  : element(elem),
    left(leftPtr),
    right(rightPtr)

{}

//--------------------------------------------------------------------

ExprTree:: ExprTree ()

// Creates an empty expression tree.

  : root(0)

{}

//--------------------------------------------------------------------

ExprTree:: ~ExprTree ()

// Frees the memory used by an expression tree.

{
    clear();
}

//--------------------------------------------------------------------

void ExprTree:: build ()

// Reads a prefix expression (consisting of single-digit, nonnegative
// integers and arithmetic operators) from the keyboard and builds the
// corresponding expression tree.

{
    buildSub(root);
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

void ExprTree:: buildSub ( ExprTreeNode *&p )

// Recursive partner of the build() function. Builds a subtree and
// sets p to point to its root.

{
    char ch;   // Input operator or number

    cin >> ch;
    p = new ExprTreeNode(ch,0,0);   // Link in node
    assert ( p != 0 );

    if ( !isdigit(ch) )             // Operator -- construct subtrees
    {
       buildSub(p->left);
       buildSub(p->right);
    }
}

//--------------------------------------------------------------------

void ExprTree:: expression () const

// Outputs the corresponding arithmetic expression in fully
// parenthesized infix form.

{
    exprSub(root);
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

void ExprTree:: exprSub ( ExprTreeNode *p ) const

// Recursive partner of the expression() function. Outputs the subtree
// pointed to by p.

{
    if ( p != 0 )
    {
       if ( !isdigit(p->element) ) cout << '(';
       exprSub(p->left);
       cout << p->element;
       exprSub(p->right);
       if ( !isdigit(p->element) ) cout << ')';
    }
}

//--------------------------------------------------------------------

float ExprTree:: evaluate () const

// Returns the value of the corresponding arithmetic expression.

{
    assert ( root != 0 );       // Requires that the tree is not empty
    return evaluateSub(root);
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

float ExprTree:: evaluateSub ( ExprTreeNode *p ) const

// Recursive partner of the evaluate() function. Returns the value of
// subtree pointed to by p.

{
    float l, r,     // Intermediate results
          result;   // Result returned

    if ( isdigit(p->element) )
       result = p->element - '0';      // Convert from char to number
    else
    {
       l = evaluateSub(p->left);       // Evaluate subtrees
       r = evaluateSub(p->right);
       switch ( p->element )           // Combine results
       {
         case '+' :  result = l + r;  break;
         case '-' :  result = l - r;  break;
         case '*' :  result = l * r;  break;
         case '/' :  result = l / r;
       }
    }
    return result;
}

//--------------------------------------------------------------------

void ExprTree:: clear ()

// Removes all the nodes from an expression tree.

{
    clearSub(root);
    root = 0;
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

void ExprTree:: clearSub ( ExprTreeNode *p )

// Recursive partner of the clear() function. Clears the subtree
// pointed to by p.

{
    if ( p != 0 )
    {
       clearSub(p->left);
       clearSub(p->right);
       delete p;
    }
}

//--------------------------------------------------------------------

void ExprTree:: showStructure () const

// Outputs an expression tree. The tree is output rotated counter-
// clockwise 90 degrees from its conventional orientation using a
// "reverse" inorder traversal. This operation is intended for testing
// and debugging purposes only.

{
    if ( root == 0 )
       cout << "Empty tree" << endl;
    else
    {
       cout << endl;
       showSub(root,1);
       cout << endl;
    }
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

void ExprTree:: showSub ( ExprTreeNode *p, int level ) const

// Recursive partner of the showStructure() function. Outputs the
// subtree whose root node is pointed to by p. Parameter level is the
// level of this node within the expression tree.

{
     int j;   // Loop counter

     if ( p != 0 )
     {
        showSub(p->right,level+1);        // Output right subtree
        for ( j = 0 ; j < level ; j++ )   // Tab over to level
            cout << "\t";
        cout << " " << p->element;        // Output element
        if ( ( p->left != 0 ) &&          // Output "connector"
             ( p->right != 0 ) )
           cout << "<";
        else if ( p->right != 0 )
           cout << "/";
        else if ( p->left != 0 )
           cout << "\\";
        cout << endl;
        showSub(p->left,level+1);         // Output left subtree
     }
}