I need to implement the ExpressionTree.cpp functions so the program runs. Expres
ID: 3682834 • Letter: I
Question
I need to implement the ExpressionTree.cpp functions so the program runs.
ExpressionTree.h
//--------------------------------------------------------------------
//
// Laboratory 8 ExpressionTree.h
//
// Class declarations for the linked implementation of the
// Expression Tree ADT -- including the recursive helpers for the
// public member functions
//
// Instructor copy with the recursive helper function declarations.
// The student version does not have those, but has a place to write
// the declarations in the private section.
//
//--------------------------------------------------------------------
#ifndef EXPRESSIONTREE_H
#define EXPRESSIONTREE_H
#include <stdexcept>
#include <iostream>
using namespace std;
template <typename DataType>
class ExprTree {
public:
// Constructor
ExprTree ();
ExprTree(const ExprTree& source);
ExprTree& operator=(const ExprTree& source);
// Destructor
~ExprTree ();
// Expression tree manipulation operations
void build ();
void expression () const;
DataType evaluate() const throw (logic_error);
void clear (); // Clear tree
void commute();
bool isEquivalent(const ExprTree& source) const;
// Output the tree structure -- used in testing/debugging
void showStructure () const;
private:
class ExprTreeNode {
public:
// Constructor
ExprTreeNode ( char elem,
ExprTreeNode *leftPtr, ExprTreeNode *rightPtr );
// Data members
char dataItem; // Expression tree data item
ExprTreeNode *left, // Pointer to the left child
*right; // Pointer to the right child
};
// Recursive helper functions for the public member functions -- insert
// prototypes of these functions here.
inline void buildHelper(ExprTreeNode*& p);
void exprHelper(ExprTreeNode* p) const;
inline DataType evalHelper(ExprTreeNode* p) const;
void clearHelper ( ExprTreeNode *p );
void showHelper ( ExprTreeNode *p, int level ) const;
void copyHelper ( ExprTreeNode *&p );
void commuteHelper(ExprTreeNode* p);
bool isEquivalentHelper(const ExprTreeNode* p,
const ExprTreeNode* q) const;
// Data member
ExprTreeNode *root; // Pointer to the root node
};
#endif // #ifndef EXPRESSIONTREE_H
ExpressionTree.cpp
//--------------------------------------------------------------------
//
// Laboratory 8 exprtree.cpp
//
//
//
//--------------------------------------------------------------------
#ifndef EXPRESSIONTREE_CPP
#define EXPRESSIONTREE_CPP
#include <stdexcept>
#include <iostream>
#include <cctype>
#include "ExpressionTree.h"
//--------------------------------------------------------------------
template <typename DataType>
ExprTree<DataType>::ExprTreeNode:: ExprTreeNode ( char nodeDataItem,
ExprTreeNode *leftPtr,
ExprTreeNode *rightPtr )
// Creates an expreesion tree node containing data item nodeDataItem,
// left child pointer leftPtr, and right child pointer rightPtr.
{
: element(elem),
left(leftPtr),
right(rightPtr)
{}
}
//--------------------------------------------------------------------
template <typename DataType>
ExprTree<DataType>:: ExprTree ()
// Creates an empty expression tree.
{
:root(0)
}
//--------------------------------------------------------------------
template <typename DataType>
ExprTree<DataType>:: ~ExprTree ()
// Frees the memory used by an expression tree.
{
clear();
}
template <typename DataType>
ExprTree<DataType>:: ExprTree ( const ExprTree &source )
// Copy constructor. Creates a copy of valueTree.
{
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <typename DataType>
ExprTree<DataType>& ExprTree<DataType>::operator=(const ExprTree& source)
// Overloads the assignment operator for any data type.
{
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <typename DataType>
void ExprTree<DataType>:: copyHelper ( ExprTreeNode *&p )
// Recursive private helper for the copy constructor and overloaded
// assignment operator. Creates a copy of the subtree pointed to by p,
// p points to the new subtree.
{
}
//--------------------------------------------------------------------
template <typename DataType>
void ExprTree<DataType>::build()
// Builds a new expression tree from standard input (cin)
{
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <>
void ExprTree<float>::buildHelper(ExprTreeNode*& p)
// Specialized function to help build trees of floats.
// Input is single digit ints or operators.
{
}
template <>
void ExprTree<bool>::buildHelper(ExprTreeNode*& p)
// Specialized function to help build boolean trees.
// Input is 0, 1, or operators.
{
}
//--------------------------------------------------------------------
template <typename DataType>
void ExprTree<DataType>::expression() const
// Public function to print out fully parenthesized expression tree.
{
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <typename DataType>
void ExprTree<DataType>::exprHelper(ExprTreeNode* p) const
// Private helper function to print out fully parenthesized expression tree.
{
}
//--------------------------------------------------------------------
template <typename DataType>
DataType ExprTree<DataType>::evaluate() const throw (logic_error)
// Public function to evaluate an expression tree.
{
DataType temp;
return temp;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <>
float ExprTree<float>::evalHelper(ExprTreeNode* p) const
// Private helper function to evaluate an expression tree with a float
// result.
{
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <>
bool ExprTree<bool>::evalHelper(ExprTreeNode* p) const
// Private helper function to evaluate an boolean expression tree with a
// bool result.
{
}
//--------------------------------------------------------------------
template <typename DataType>
void ExprTree<DataType>:: clear ()
// Removes all the nodes from an expression tree.
{
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <typename DataType>
void ExprTree<DataType>:: clearHelper ( ExprTreeNode *p )
// Recursive helper for the clear() function. Clears the subtree
// pointed to by p.
{
}
//--------------------------------------------------------------------
template <typename DataType>
void ExprTree<DataType>::commute()
// Public operator to commute the tree.
{
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <typename DataType>
void ExprTree<DataType>::commuteHelper(ExprTreeNode* p)
// Private recursive helper function to commute the tree.
{
}
//--------------------------------------------------------------------
template <typename DataType>
bool ExprTree<DataType>::isEquivalent(const ExprTree<DataType>& source) const
// Public operator to determine whether two expression trees are equivalent.
{
return false;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <typename DataType>
bool ExprTree<DataType>::isEquivalentHelper(const ExprTreeNode* x,
const ExprTreeNode* y) const
// Private recursive assistant function to determine whether two expression
// trees are equivalent.
{
return false;
}
template <typename DataType>
void ExprTree<DataType>:: 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.
{
// No isEmpty function in this class. Add a private one if you wish.
if ( root == 0 )
cout << "Empty tree" << endl;
else
{
cout << endl;
showHelper(root,1);
cout << endl;
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <typename DataType>
void ExprTree<DataType>:: showHelper ( ExprTreeNode *p, int level ) const
// Recursive helper for 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 )
{
showHelper(p->right,level+1); // Output right subtree
for ( j = 0 ; j < level ; j++ ) // Tab over to level
cout << " ";
cout << " " << p->dataItem; // Output dataItem
if ( ( p->left != 0 ) && // Output "connector"
( p->right != 0 ) )
cout << "<";
else if ( p->right != 0 )
cout << "/";
else if ( p->left != 0 )
cout << "\";
cout << endl;
showHelper(p->left,level+1); // Output left subtree
}
}
//--------------------------------------------------------------------
#endif // #ifndef EXPRESSIONTREE_CPP
show.cpp
//--------------------------------------------------------------------
//
// Laboratory 8 show8.cpp
//
// Linked implementation of the showStructure operation for the
// Expression Tree ADT
//
//--------------------------------------------------------------------
#include "ExpressionTree.h"
//--------------------------------------------------------------------
template <typename DataType>
void ExprTree<DataType>:: 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 ( isEmpty() )
cout << "Empty tree" << endl;
else
{
cout << endl;
showHelper(root,1);
cout << endl;
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <typename DataType>
void ExprTree<DataType>:: showHelper ( ExprTreeNode *p, int level ) const
// Recursive helper for 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 )
{
showHelper(p->right,level+1); // Output right subtree
for ( j = 0 ; j < level ; j++ ) // Tab over to level
cout << " ";
cout << " " << p->dataItem; // Output dataItem
if ( ( p->left != 0 ) && // Output "connector"
( p->right != 0 ) )
cout << "<";
else if ( p->right != 0 )
cout << "/";
else if ( p->left != 0 )
cout << "\";
cout << endl;
showHelper(p->left,level+1); // Output left subtree
}
}
test.cpp
//--------------------------------------------------------------------
//
// Laboratory 8 test8.cpp
//
// Test program for the operations in the Expression Tree ADT
//
//--------------------------------------------------------------------
#include <iostream>
#include <stdexcept>
using namespace std;
//#include "ExprTree.cpp"
#include "ExpressionTree.cpp"
#include "config.h"
//--------------------------------------------------------------------
// Function prototype
template <typename DataType>
void dummy ( ExprTree<DataType> copyTree ); // copyTree is passed by value
//--------------------------------------------------------------------
int main()
{
#if !LAB8_TEST1 || LAB8_TEST2 || LAB8_TEST3
// Don't do this if testing boolean tree, unless also testing programming
// exercises 2 or 3 (for which this section is mostly needed).
// The tricky part occurs if testing exercise 1 and (2 or 3), or if
// someone is trying to test the basic class and one of the other exercises
// in parallel. Hence the #if expression above.
cout << "Start of testing the basic expression tree" << endl;
ExprTree<float> testExpression; // Test expression
cout << endl << "Enter an expression in prefix form : ";
testExpression.build();
testExpression.showStructure();
testExpression.expression();
cout << " = " << testExpression.evaluate() << endl;
// Test the copy constructor.
dummy(testExpression);
cout << endl << "Original tree:" << endl;
testExpression.showStructure();
#endif
#if LAB8_TEST1
cout << "Start of testing the boolean expression tree" << endl;
ExprTree<bool> boolTree;
cout << endl << "Enter a boolean expression in prefix form : ";
boolTree.build();
boolTree.showStructure();
boolTree.expression();
cout << " = " << boolTree.evaluate() << endl;
cout << "** End of testing the boolean expression tree" << endl;
#endif
#if LAB8_TEST2
cout << "Start of testing commute()" << endl;
testExpression.commute();
cout << endl << "Fully commuted tree: " << endl;
testExpression.showStructure();
testExpression.expression();
cout << " = " << testExpression.evaluate() << endl;
cout << "End of testing commute()" << endl;
#endif
#if LAB8_TEST3
cout << "Start of testing isEquivalent()" << endl;
ExprTree<float> same = testExpression;
cout << "same is equal (tests copy constructor) ? ";
cout << (same.isEquivalent(testExpression) ? "Yes" : "No") << endl;
ExprTree<float> empty;
cout << "empty is equal? ";
cout << (empty.isEquivalent(testExpression) ? "Yes" : "No") << endl;
ExprTree<float> userExpression;
cout << "Enter another expression in prefix form: ";
userExpression.build();
cout << "new expression is equal? ";
cout << (userExpression.isEquivalent(testExpression) ? "Yes" : "No") << endl;
cout << "** End of testing isEquivalent()" << endl;
#endif
#if !LAB8_TEST1 && !LAB8_TEST2 && !LAB8_TEST3
// Don't bother with this if testing any of the programming exercises
cout << endl << "Clear the tree" << endl;
testExpression.clear();
testExpression.showStructure();
cout << "** End of testing the basic expression tree" << endl;
#endif
return 0;
}
//--------------------------------------------------------------------
template <typename DataType>
void dummy ( ExprTree<DataType> copyTree )
// Dummy routine that is passed an expression tree using call by
// value. Outputs copyTree and clears it.
{
cout << endl << "Copy of tree: " << endl;
copyTree.showStructure();
copyTree.clear();
cout << "Copy cleared: " << endl;
copyTree.showStructure();
}
config.h
/**
* Expression Tree class (Lab 8) configuration file.
* Activate test #N by defining the corresponding LAB8_TESTN to have the value 1.
*/
#define LAB8_TEST1 1 // Programming Exercise 1: Logic tree activator
#define LAB8_TEST2 1 // Programming Exercise 2: Commute operation
#define LAB8_TEST3 1 // Programming Exercise 3: isEquivalent operation
Explanation / Answer
See functions below:
//--------------------------------------------------------------------
template <typename DataType>
ExprTree<DataType>::ExprTreeNode:: ExprTreeNode ( char nodeDataItem,
ExprTreeNode *leftPtr,
ExprTreeNode *rightPtr )
// Creates an expreesion tree node containing data item nodeDataItem,
// left child pointer leftPtr, and right child pointer rightPtr.
{
dataItem=nodeDataItem;
left=leftPtr;
right=rightPtr;
}
//--------------------------------------------------------------------
template <typename DataType>
ExprTree<DataType>:: ExprTree ()
// Creates an empty expression tree.
{
root=NULL;
}
//--------------------------------------------------------------------
template <typename DataType>
ExprTree<DataType>:: ~ExprTree ()
// Frees the memory used by an expression tree.
{
clear();
}
template <typename DataType>
ExprTree<DataType>:: ExprTree ( const ExprTree &source )
// Copy constructor. Creates a copy of valueTree.
{
copyHelper(source.root);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <typename DataType>
ExprTree<DataType>& ExprTree<DataType>::operator=(const ExprTree& source)
// Overloads the assignment operator for any data type.
{
copyHelper(source.root);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <typename DataType>
void ExprTree<DataType>:: copyHelper( ExprTreeNode *&p )
// Recursive private helper for the copy constructor and overloaded
// assignment operator. Creates a copy of the subtree pointed to by p,
// p points to the new subtree.
{
this->root=p;
copyHelper(p->left);
copyHelper(p->right);
}
//--------------------------------------------------------------------
template <typename DataType>
void ExprTree<DataType>::build()
// Builds a new expression tree from standard input (cin)
{
buildHelper(root);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <float>
void ExprTree<float>::buildHelper(ExprTreeNode* &p)
// Specialized function to help build trees of floats.
// Input is single digit ints or operators.
{
char symbol;
cin>>symbol;
while(symbol!=' ')
{
if(symbol=='+'||symbol=='-'||symbol=='*'||symbol=='/')
{
p=new ExprTreeNode(symbol,NULL,NULL);
buildHelper(p->left);
buildHelper(p->right);
}
else if(isdigit(symbol))
{
p=new ExprTreeNode((float)(symbol-'0'),NULL,NULL);
}
}
}
template <bool>
void ExprTree<bool>::buildHelper(ExprTreeNode* &p)
// Specialized function to help build boolean trees.
// Input is 0, 1, or operators.
{
char symbol;
cin>>symbol;
while(symbol!=' ')
{
if(symbol=='&'||symbol=='|'||symbol=='^')
{
p=new ExprTreeNode(symbol,NULL,NULL);
buildHelper(p->left);
buildHelper(p->right);
}
else if(isdigit(symbol))
{
int val=symbol-'0';
if(val==0 || val==1)
p=new ExprTreeNode((bool)(val),NULL,NULL);
}
}
}
//--------------------------------------------------------------------
template <typename DataType>
void ExprTree<DataType>::expression() const
// Public function to print out fully parenthesized expression tree.
{
exprHelper(root);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <typename DataType>
void ExprTree<DataType>::exprHelper(ExprTreeNode* p) const
// Private helper function to print out fully parenthesized expression tree.
{
if(p!=NULL)
{
exprHelper(p->left);
cout<<"("<<p->dataItem<<")"<<endl;
exprHelper(p->right);
}
}
//--------------------------------------------------------------------
template <typename DataType>
DataType ExprTree<DataType>::evaluate() const throw (logic_error)
// Public function to evaluate an expression tree.
{
DataType temp=evalHelper(root);
return temp;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <>
float ExprTree<float>::evalHelper(ExprTreeNode* p) const
// Private helper function to evaluate an expression tree with a float
// result.
{
if(p->left==NULL && p->right==NULL)
{
return ((float)(p->dataItem-'0'));
}
else
{
float value=0.0;
float op1=evalHelper(p->left);
float op2=evalHelper(p->right);
char optr=p->dataItem;
switch(optr)
{
case '+':
value=op1+op2;
break;
case '-':
value=op1-op2;
break;
case '*':
value=op1*op2;
break;
case '/':
value=op1/op2;
break;
default:
cerr<<"Error message: Something went wrong. Exiting..."<<endl;
exit(1);
}
return value;
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <>
bool ExprTree<bool>::evalHelper(ExprTreeNode* p) const
// Private helper function to evaluate an boolean expression tree with a
// bool result.
{
if(p->left==NULL && p->right==NULL)
{
return ((bool)(p->dataItem-'0'));
}
else
{
bool value=false;
bool op1=evalHelper(p->left);
bool op2=evalHelper(p->right);
char optr=p->dataItem;
switch(optr)
{
case '&':
value=op1&op2;
break;
case '|':
value=op1|op2;
break;
case '^':
value=op1^op2;
break;
default:
cerr<<"Error message: Something went wrong. Exiting..."<<endl;
exit(1);
}
return value;
}
}
//--------------------------------------------------------------------
template <typename DataType>
void ExprTree<DataType>:: clear ()
// Removes all the nodes from an expression tree.
{
clearHelper(root)
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template <typename DataType>
void ExprTree<DataType>:: clearHelper ( ExprTreeNode *p )
// Recursive helper for the clear() function. Clears the subtree
// pointed to by p.
{
if(p!=NULL)
{
clear(p->left);
clear(p->right);
delete p;
}
}
//-----------------------------------------------------------------------------------