CSCI 340 Assignment 3

Purpose

This assignment reviews the binary tree data structure and the STL vector class and introduces the STL stack and queue classes.

Assignment

You will implement a binary expression tree class. You will build the tree from a postfix expression string using a stack.

Program

You will need to write the header files and source code for three classes:

Class Variable

The Variable data is used to store the name and value of a postfix expression variable. To simplify coding, the only variable names used in this assignment will be single capital letters.

Because the data members of a Variable must be frequently accessed by the ExprTree implementation, the Variable class should declare the ExprTree class to be a friend.

A Variable contains two data members. The first is a char that contains the variable name. The second is a double that contains the variable's current value.

Constructor for Variable

Variable has only one constructor, which takes two parameters, a char and a double. These parameters are used to initialize the data members of the class.

Overloaded << operator for Variable

Overload the << operator for the Variable class to print the two data members of a variable, separated by a single space. As usual, you will need to declare your overloaded operator function to be a friend.

Class TNode

The TNode data structure is used as a building block to create a linked version of a binary expression tree.

Because the data members of a TNode must be frequently accessed by the ExprTree implementation, the TNode should declare the ExprTree class to be a friend.

A TNode contains four data members. The first is a char that specifies the type of operator or operand stored in the tree node. The second is a double containing the value of an operand stored in the node. The third and fourth are pointers to a TNode, the roots of the left and right subtrees of the node in the binary tree.

Constructor for TNode

TNode has only one constructor, which takes two parameters, a char and a double. Give the second parameter a default value of 0.0. The two constructor parameters are used to initialize the first two data members of the class; the two pointer data members should be initialized to a null value.

Overloaded << operator for TNode

Overload the << operator for the TNode class to print the data members of an expression tree node. If the type of the node is equal to '#', print the value data member only. Otherwise, print only the type of the node. As usual, you will need to declare your overloaded operator function to be a friend.

Class ExprTree

The ExprTree class stores the root of a binary expression tree and an external list of the expression variables.

This class contains two data members. The first is a pointer to a TNode, the root node of the expression tree. The second is an STL vector of Variable objects containing the variable names in the expression tree and their values.

Note: In implementing this class, you may want some additional helper functions, especially if you use recursion. You are free to add any private methods you wish to the ExprTree class. You may not add additional data members. You may not make any changes to the TNode class.

Constructors for ExprTree

The default constructor for the class should initialize the root pointer to null. You should also write a second constructor that takes a reference to a constant C++ string as its sole parameter. This constructor should call the build() method outlined below, passing the string to it.

Copy constructor for ExprTree

The copy constructor takes a reference to a constant ExprTree object as its parameter and should be implemented in the usual fashion for a binary tree. In addition to the tree itself, you will also need to copy the list of variables. This can be accomplished by assigning the variable list of the tree to the variable list of the new tree, since the vector class has a built-in overloaded assignment operator.

Destructor for ExprTree

This function calls the destroy() method described below, passing it the root of the expression tree. The vector of variables already has its own destructor that will be called automatically.

ExprTree::clear()

This method returns nothing and takes no parameters. It clears the binary expression tree, releasing all of the dynamic memory associated with the tree. It does not alter the vector of variables. It should call the destroy() method, passing it the root of the tree, and then set the root to a null value.

ExprTree::destroy()

This method returns nothing and takes a pointer to an expression tree node as its sole parameter. The method should traverse the tree and free all of the nodes. The logic here is basically a slightly modified postorder traversal, so it is easiest to write this as a recursive function. This method will not be called from outside the ExprTree class, so make it private.

Overloaded assignment operator for ExprTree

Standard approach applies. As with the copy constructor, the vector of variables may be copied using a normal assignment statement.

ExprTree::build()

This method returns nothing and takes a reference to a constant string as its parameter. The string will contain a postfix expression, with the tokens of the expression separated by spaces. The method should build a binary expression tree from the postfix expression string using an STL stack to temporarily store the addresses of the tree nodes as the tree is built.

There are a number of possible ways to break a string into individual tokens in C/C++, and you may use any method you like. One way is outlined in the Implementation Hints below.

Once all tokens in the expression string have been processed, pop an address off the stack and store it as the root of the expression tree.

ExprTree::evaluate()

This method returns a double and takes no parameters. It should compute and return the value of the expression stored in the tree, or 0.0 if the tree is empty. The logic described here is once again a modified postorder traversal, so you will most likely want to write a recursive helper function to do the work. All of the operands (literal numbers and variable names) in the expression tree are stored in leaf nodes, while the operators are stored in non-leaf nodes.

ExprTree::printInorder()
ExprTree::printPostorder()
ExprTree::printLevel()

Print the nodes of the tree to standard output in inorder, postorder, and level-by-level fashion respectively. The first two are easy to implement using recursive helper methods. For the inorder traversal, we will print the infix version of the expression in fully parenthesized form. To do this, print "( ", traverse the left subtree, print the current node contents followed by a space, traverse the right subtree, and finally print ") ".

The level-by-level traversal should be implemented iteratively (i.e., non-recursively) using an STL queue object to store the node addresses as the tree is traversed.

ExprTree::setVariable()

This method returns nothing and takes two parameters, a char variable name and a double variable value. The method should declare an appropriate iterator and use it to perform a linear search of the variable list vector for the variable name passed in as a parameter. If the name is found, replace the current value stored for the variable with the new value passed in as a parameter. If the name is not found, create a new Variable object with the new variable name and value passed in as parameters and add it to the end of the vector.

ExprTree::getVariable()

This method returns a double and takes one parameter, a char variable name. The method should declare an appropriate iterator and use it to perform a linear search of the variable list vector for the variable name passed in as a parameter. If the name is found, return the value associated with it. If not, return 0.0.

ExprTree::printVariables()

This method returns nothing and takes no parameters. It should declare an appropriate iterator and use it to traverse the variable list vector, printing the values of the Variable objects stored there.

Implementation Hints

One method to break a C++ string into individual tokens is to use a string stream. Since a string is just a series of characters (just like a file or input typed at the keyboard), you can create a stream object and associate it with a C++ string, e.g.:

   istringstream ist(expressionString);   // create an input string stream
   string token;         // string to hold individual token

   while (ist >> token)  // read a single token from the expression string stream
      {            
      // process the token
      }

The istringstream class can be found in the C++ header file <sstream>.

You can use an iterator or subscript with C++ strings. You can also use some of the higher-level functions available. (You can obtain the length of a string from the length() method of string.)

A C++ string object can be converted to a C-style null-terminated string using the c_str() method string. There are several C functions that will convert a C-style string to a double, including atof(), strtod(), and sscanf(). Check the online man pages for details of these functions.

There are also many web sites available that cover the C++ Standard Template Library classes and the C standard library functions; see the course web page for some useful links.

Submission