Program 5 - Expression Trees

ITSE 2445 - Data Structures and
ITSE 2445 Data Structures
Bob Comer, Professor of Computer Studies

Program 5 - Expression Trees

Final version (unless I find typographical errors)

Be sure to read through Chapter 10 of the textbook before starting this assignment.

This assignment is a simplified version of Programming Project 1 at the end of Chapter 10 of the Main and Savitch textbook (pages 529-530). Read the problem from the book first.

To simplify this problem, I created an expr_tree_node class by rewriting the binary_tree_node. For simplicity, I created a class instead of a template.

As described in the book, an expression tree has 2 kinds of nodes. Nonleaf nodes contain an operator and leaf nodes contain a floating-point number. Since all nodes in a binary tree must have the same data type, I chose to make the data in an expression tree node a class with two data members - an operator (char) and a floating-point value (double). This class is called expr_node_data. When you retrieve the data from a node in the expression tree, it is an expr_tree_node object. To retrieve the operator from a non-leaf node pointed to by ptr, use:

ptr->data( ).get_op( )

Likewise, you can use the get_number( ) member function to retrieve the floating-point value from a leaf node.

I am providing code below:

A sample driver program.
Code for the expr_node_data and expr_tree_node classes. The code is divided into one header file and one implementation file.
The implementation file includes a function called print_expr_tree( ) that replaces the print( ) function from the binary_tree_node class. This function "knows" how to print an expression tree. This function allows you to check that the expression tree was built correctly.
The implementation file also includes a function called build that will input a fully-parenthesized infix expression and create an expression tree. This function uses the algorithm presented in the Basic Calculator program from Chapter 7.

Your assignment is to first try out the code below to be sure that you understand it. Then you only have to implement the recursive evaluate( ) function. You only need to write internal documentation (comments) for the code that you write.

Driver program

// Sample driver program for expression tree class

#include <cstdlib>    // Provides EXIT_SUCCESS
#include <iostream>   // Provides cout, cin, peek, ignore
#include "exprtree.h"
using namespace std;
using namespace expr_tree_10;

int main( )
{
   expr_tree_node *expr_ptr;

   cout << "Type a fully parenthesized arithmetic expression:" << endl;
   expr_ptr = build( );
   print_expr_tree( expr_ptr, 0 );
   cout << "The value of the expression is " << evaluate( expr_ptr )
        << endl;
   return EXIT_SUCCESS;
}

Header file for expression tree classes

// File: exprtree.h

#ifndef EXPRTREE_H
#define EXPRTREE_H
#include <cstdlib>  // Provides NULL and size_t

namespace expr_tree_10
{

	// class for expression node data
	class expr_node_data
	{
	public:
		expr_node_data( )
		{
			op = '\0';
			number = 0.0;
		}
		expr_node_data( char init_op )
		{
			op = init_op;
			number = 0.0;
		}
		expr_node_data( double init_num )
		{
			op = '\0';
			number = init_num;
		}
		void set_op( char new_op )
		{
			op = new_op;
			number = 0.0;
		}
		void set_number( double new_num )
		{
			number = new_num;
			op = '\0';
		}
		char get_op( ) const { return op; }
		double get_number( ) const { return number; }
	private:
		char op;
		double number;
	};

    class expr_tree_node
    {
    public:
	// TYPEDEF
	typedef expr_node_data value_type;
	// CONSTRUCTOR
	expr_tree_node(
	    const value_type& init_data = value_type( ),
	    expr_tree_node* init_left = NULL,
	    expr_tree_node* init_right = NULL
	)
	{ 
      	    data_field = init_data; 
	    left_field = init_left; 
	    right_field = init_right;
	}
	// MODIFICATION MEMBER FUNCTIONS
	value_type& data( ) { return data_field; }
	expr_tree_node*& left( ) { return left_field; }
	expr_tree_node*& right( ) { return right_field; }
	void set_data(const value_type& new_data) { data_field = new_data; }
	void set_left(expr_tree_node* new_left) { left_field = new_left; }
	void set_right(expr_tree_node* new_right) { right_field = new_right; }
	// CONST MEMBER FUNCTIONS
	const value_type& data( ) const { return data_field; }
	const expr_tree_node* left( ) const { return left_field; }
	const expr_tree_node* right( ) const { return right_field; }
	bool is_leaf( ) const 
	    { return (left_field == NULL) && (right_field == NULL); }
    private:
	value_type data_field;
	expr_tree_node *left_field;
	expr_tree_node *right_field;
    };

 // NON-MEMBER FUNCTIONS for the expr_tree_node:
    template <class Process, class BTNode>
    void inorder(Process f, BTNode* node_ptr); 

    template <class Process, class BTNode>
    void preorder(Process f, BTNode* node_ptr);

    template <class Process, class BTNode>
    void postorder(Process f, BTNode* node_ptr); 

    void print_expr_tree(expr_tree_node* node_ptr, int depth);

    void tree_clear(expr_tree_node*& root_ptr);

    expr_tree_node* tree_copy(const expr_tree_node* root_ptr);

    size_t tree_size(const expr_tree_node* node_ptr);
    
    expr_tree_node* build( );
    
    double evaluate( const expr_tree_node* root_ptr );
	
}

#endif

Implementation file for expression tree classes

// FILE: exprtree.cpp
//
#include <cassert>    // Provides assert
#include <cstdlib>    // Provides NULL, size_t
#include <iomanip>    // Provides std::setw
#include <iostream>   // Provides std::cout
#include <stack>
#include "exprtree.h"
using namespace std;
namespace expr_tree_10
{
    template <class Process, class BTNode>
    void inorder(Process f, BTNode* node_ptr)
    // Library facilities used: cstdlib
    {
        if (node_ptr != NULL)
        {
            inorder(f, node_ptr->left( ));
            f( node_ptr->data( ) );
            inorder(f, node_ptr->right( ));
        }
    }

    template <class Process, class BTNode>
    void postorder(Process f, BTNode* node_ptr)
    // Library facilities used: cstdlib
    {
        if (node_ptr != NULL)
        {
            postorder(f, node_ptr->left( ));
            postorder(f, node_ptr->right( ));
            f(node_ptr->data( ));
        }
    }

    template <class Process, class BTNode>
    void preorder(Process f, BTNode* node_ptr)
    // Library facilities used: cstdlib
    {
        if (node_ptr != NULL)
        {
            f( node_ptr->data( ) );
            preorder(f, node_ptr->left( ));
            preorder(f, node_ptr->right( ));
        }
    }

    void print_expr_tree( expr_tree_node* node_ptr, int depth )
    // Library facilities used: iomanip, iostream, stdlib
    {
        if (node_ptr != NULL)
        {
            print_expr_tree(node_ptr->right( ), depth+1);
            std::cout << std::setw(4*depth) << ""; // Indent 4*depth spaces
            if ( node_ptr->is_leaf( ) )
                std::cout << node_ptr->data( ).get_number( ) << std::endl;
            else
                std::cout << node_ptr->data( ).get_op( ) << std::endl;
            print_expr_tree(node_ptr->left( ),  depth+1);
        }
    }    
	
    void tree_clear(expr_tree_node*& root_ptr)
    // Library facilities used: cstdlib
    {
	if (root_ptr != NULL)
	{
	    tree_clear( root_ptr->left( ) );
	    tree_clear( root_ptr->right( ) );
	    delete root_ptr;
	    root_ptr = NULL;
	}
    }

    expr_tree_node* tree_copy(const expr_tree_node* root_ptr)
    // Library facilities used: cstdlib
    {
	expr_tree_node *l_ptr;
	expr_tree_node *r_ptr;

	if (root_ptr == NULL)
	    return NULL;
	else
	{
	    l_ptr = tree_copy( root_ptr->left( ) );
	    r_ptr = tree_copy( root_ptr->right( ) );
	    return
		new expr_tree_node( root_ptr->data( ), l_ptr, r_ptr);
	}
    }

    size_t tree_size(const expr_tree_node* node_ptr)
    // Library facilities used: cstdlib
    {
        if (node_ptr == NULL)
            return 0;
        else 
            return 
	    1 + tree_size(node_ptr->left( )) + tree_size(node_ptr->right( ));
     }
    
    /********************************************************************************
    // Non-member function evaluate
    // Precondition: root_ptr points to an expression tree with at least one node
    // Postcondition: the return value is the value of the expression tree.
    /********************************************************************************/

    double evaluate( const expr_tree_node* root_ptr )
    {
        // evaluate code goes here
    }

    expr_tree_node* build( )
    // Library facilities used: iostream, stack
    {
        const char DECIMAL = '.';
        const char RIGHT_PARENTHESIS = ')';
        stack<expr_tree_node *> nodes;
        stack<char> operations;
        double num;
        expr_node_data data;
        char ch;
	
        expr_tree_node *left_operand, *right_operand;
    
        while ( cin.peek( ) != '\n' ) 
        {
            if (isdigit(cin.peek( )) || (cin.peek( ) == DECIMAL))
            {
            // process a numeric value
                cin >> num;
                data.set_number( num );
                nodes.push( new expr_tree_node( data ) );
            }
            else if (strchr("+-/*", cin.peek( )) != NULL)
            {
                cin >> ch;
                operations.push( ch );
            }
            else if ( cin.peek( ) == RIGHT_PARENTHESIS)
            {
                cin.ignore( );
                right_operand = nodes.top( );
                nodes.pop( );
                left_operand = nodes.top( );
                nodes.pop( );
                data.set_op( operations.top( ));
                nodes.push( 
                    new expr_tree_node( data, left_operand, right_operand ) );
                operations.pop( );
            }
            else
                cin.ignore( );
        }

        return nodes.top( );
}

}