Requirements

In this sub-project, you will implement the class ExpressionTree.

An expression tree is a binary tree which stores either:

• An operator and two non-empty sub trees, or
• A value (an integer).

Class Specifications

UML Class Diagram

Expression Tree
- element:Integer - left_tree:ExpressionTree - right_tree:ExpressionTree
+ create( in v:Integer = 0, in l:ExpressionTree = 0, in r:ExpressionTree = 0 ):ExpressionTree + evaluate():Integer + in_fix( in parent_op:Integer, in is_left:Boolean ) + reverse_polish() + is_leaf():Boolean + destroy()

Description

A class which stores an integer and two pointers to other expression trees. Either a node is full (in which case, it stores a value which identifies the type of operator) or it is a leaf node, in which case it stores an integer. For run time requirements, n is the number of nodes in the sub tree defined by this node.

Member Variables

The three member variables are:

• An integer either an integer or an operator ID, and
• Two pointers to ExpressionTree objects, referred to as the left sub-tree and right sub-tree, respectively.

Class Constants

The class has four static constants:

• ExpressionTree::PLUS
• ExpressionTree::MINUS
• ExpressionTree::TIMES
• ExpressionTree::DIVIDE

You may use these in creating your expression tree.

Member Functions

Constructors

ExpressionTree( int = 0, ExpressionTree * = 0, ExpressionTree * = 0 )

This constructor takes three arguments: an integer and two pointers which point to ExpressionTree objects. (O(1))

Destructor

The destructor deletes the left and right sub trees if they are not 0.

Accessors

This class has four accessors:

int evaluate() const

If the node is a leaf node, return the value. Otherwise, the node represents an operator, in which case, you perform the operation on the evaluated sub trees. If a division is being performed and the denominator is zero, a division_by_zero exception is thrown. (O(n))

void in_fix( int, bool ) const

If the node is a leaf node, print the node. Otherwise, print the expression using in-fix notation. This is specified on the page for Expression. The arguments may be used to pass information from the parent node to a child. (O(n))

void reverse_polish() const

If the node is a leaf node, print the node. Otherwise, print the left sub-tree, then the right sub-tree, and then print the operator (+, -, *, or /, as appropriate). Each of these should be followed by a space. (O(n))

bool is_leaf() const

Returns true if the node is a leaf noder. (O(1))

Mutators

This class has no member functions which modify the member variables.

Friends

This class has no friends.