CSCI373 Expression Tree

Problem Description

A binary expression tree is a specific kind of a binary tree used to represent expressions. Two common types of expressions that a binary expression tree can represent are algebraic and boolean. These trees can represent expressions that contain both unary and binary operators.

Task

Implement the class ExpressionTree as a binary tree which stores either:

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

Runtime

The amortized run time of each member function is specified in parentheses at the end of the description.

Class Specifications

UML Class Diagram

A skeleton for this class is provided in the source directory in the file ExpressionTree.h.

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.

Operations

Algebraic operations defined in the enumeration Operation. This enumeration contains enumerators with the following values:

• PLUS = -1
• MINUS = -2
• TIMES = -3
• DIVIDE = -4

You may use these in creating your expression tree.

Member Variables

The ExpressionTree class has tree member variable:

• An integer either a positive integer or an operator ID, and
• Two unique pointers to ExpressionTree objects, referred to as the left subtree and right subtree, respectively.

Member Functions

Constructor

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

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

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 runtime_error exception is thrown. (O(n))

void infix() const

• If the node is a leaf node, print the node. Otherwise, print the expression using infix notation. 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 node. (O(1))

Mutators

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

Friends

This class has no friends.

Test Driver Output

The test driver program contains several test expressions which verify correctness of the expression tree implementation. Following test driver output is produced for a correctly implemented ExpressionTree class.

Expression in infix notation: ( 1 + ( 3 * 2 ) )
Expression in postfix notation: 1 3 2 * +
Expression value: 7
Expression in infix notation: ( ( 1 - ( ( 2 + 3 ) + ( ( 4 - ( 5 * 6 ) ) * 7 ) ) ) + ( 8 * 9 ) )
Expression in postfix notation: 1 2 3 + 4 5 6 * - 7 * + - 8 9 * +
Expression value: 250
Expression in infix notation: ( ( ( ( ( 1 - 2 ) + 3 ) + 4 ) - ( ( 5 * 6 ) * 7 ) ) + ( 8 * 9 ) )
Expression in postfix notation: 1 2 - 3 + 4 + 5 6 * 7 * - 8 9 * +
Expression value: -132
Expression in infix notation: ( ( 11 * 2 ) / ( 3 + 4 ) )
Expression in postfix notation: 11 2 * 3 4 + /
Expression value: 3
Expression in infix notation: ( ( 11 * 2 ) / ( 4 - 4 ) )
Expression in postfix notation: 11 2 * 4 4 - /
Expression value: Error: Division by zero
Done!

Note: The output might vary depending on your implementation.

Starter Code

TestDriver.cpp

/*************************************************
* ExpressionTree Tester
*
* DO NOT EDIT THIS FILE
*************************************************/

#include < iostream>
#include "csci373.h"
#include "ExpressionTree.h"

#define VL(v) (new ExpressionTree(v))
#define OP(l,o,r) (new ExpressionTree(o,l,r))

int main()
{
csci373::allocation_table.start_recording();

ExpressionTree* expressions[5] = {
// infx: ( 1 + ( 3 × 2 ) )
// post: 1 3 2 × +
// eval: 7
OP(VL(1), PLUS, OP(VL(3), TIMES, VL(2))),
// infx: 1 − (2 + 3 + (4 − 5 × 6) × 7) + 8 × 9
// post: 1 2 3 + 4 5 6 × −7 × + − 8 9 × +
// eval: 250
OP(OP(VL(1), MINUS, OP(OP(VL(2), PLUS, VL(3)), PLUS,
OP(OP(VL(4), MINUS, OP(VL(5), TIMES, VL(6))), TIMES, VL(7)))
), PLUS, OP(VL(8), TIMES, VL(9))),
// infx: 1 - 2 + 3 + 4 - 5 × 6 × 7 + 8 × 9
// post: 1 2 - 3 + 4 + 5 6 × 7 × - 8 9 × +
// eval: -132
OP(OP(OP(OP(OP(VL(1), MINUS, VL(2)), PLUS, VL(3)), PLUS, VL(4)),
MINUS, OP(OP(VL(5), TIMES, VL(6)), TIMES, VL(7))),
PLUS, OP(VL(8), TIMES, VL(9))),
// infx: (11 × 2 )/ (3 + 4)
// post: 11 2 × 3 4 + /
// eval: 3
OP(OP(VL(11), TIMES, VL(2)), DIVIDE, OP(VL(3), PLUS, VL(4))),
// infx: (11 × 2 )/ (4 - 4)
// post: 11 2 × 4 4 - /
// eval: error
OP(OP(VL(11), TIMES, VL(2)), DIVIDE, OP(VL(4), MINUS, VL(4)))
};

for (auto ex : expressions){
std::cout << "Expression in infix notation: ";
ex->infix();
std::cout << "nExpression in postfix notation: ";
ex->reverse_polish();
try {
std::cout << "nExpression value: " << ex->evaluate() << std::endl;
}
catch (std::runtime_error &e) {
std::cout << "Error: " << e.what() << std::endl;
}
delete ex;
}

std::cout << "Done!" << std::endl;
csci373::allocation_table.stop_recording();
csci373::allocation_table.summary();
csci373::allocation_table.details();
return 0;
}

ExpressionTree.h

#pragma once

#include < iostream>
#include < memory>
#include < exception>

enum Operation { PLUS = -1, MINUS = -2, TIMES = -3, DIVIDE = -4 };

class ExpressionTree {
private:
int value;
std::unique_ptr left_tree;
std::unique_ptr right_tree;

public:
ExpressionTree(int = 0, ExpressionTree * = nullptr, ExpressionTree * = nullptr);

// Accessors

bool is_leaf() const;
int evaluate() const;
void infix() const;
void reverse_polish() const;
};