C++ Programming. Please only answer if you can do the ENTIRE problem. DO NOT MAK
ID: 3854754 • Letter: C
Question
C++ Programming. Please only answer if you can do the ENTIRE problem. DO NOT MAKE YOUR OWN CPP FILES, VARIABLES, ETC. UPLOAD ALL OF THE EXACT .CPP AND .H FILES AS I HAVE THEM JUST COMPLETED. Reattach all 4 files I have below even if you didn't have to edit one. Program MUST compile and all these insructions followed in order for me to give a thumbs up.
Parts to complete:
- implement the Expression Tree ADT
- implement the following operations:
- constructor, copy constructor, assignment operator, destructor
- Exercise 2 (commute operation)
- build, expression, evaluate
- clear
test8.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
system("PAUSE");
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();
}
ExpressionTree.cpp
#include "ExpressionTree.h"
template <typename DataType>
ExprTree<DataType>::ExprTreeNode::ExprTreeNode ( char elem, ExprTreeNode *leftPtr, ExprTreeNode *rightPtr )
{
}
template <typename DataType>
ExprTree<DataType>::ExprTree ()
{
}
template <typename DataType>
ExprTree<DataType>::ExprTree(const ExprTree& source)
{
}
template <typename DataType>
ExprTree<DataType>& ExprTree<DataType>::operator=(const ExprTree& source)
{
}
template <typename DataType>
void ExprTree<DataType>::copyHelper(ExprTreeNode *&p)
{}
template <typename DataType>
ExprTree<DataType>::~ExprTree ()
{
}
template <typename DataType>
void ExprTree<DataType>::build ()
{
}
template <>
void ExprTree<float>::buildHelper(ExprTreeNode*& p)
{}
template <>
void ExprTree<bool>::buildHelper(ExprTreeNode*& p)
{}
template <typename DataType>
void ExprTree<DataType>::expression () const
{
}
template <typename DataType>
void ExprTree<DataType>::exprHelper(ExprTreeNode* p) const
{}
template <typename DataType>
DataType ExprTree<DataType>::evaluate() const throw (logic_error)
{
DataType temp;
return temp;
}
template <>
float ExprTree<float>::evalHelper(ExprTreeNode* p) const
{
float temp;
return temp;
}
template <>
bool ExprTree<bool>::evalHelper(ExprTreeNode* p) const
{
bool temp;
return temp;
}
template <typename DataType>
void ExprTree<DataType>::clear ()
{
}
template <typename DataType>
void ExprTree<DataType>::clearHelper(ExprTreeNode *p)
{}
template <typename DataType>
void ExprTree<DataType>::commute()
{
}
template <typename DataType>
void ExprTree<DataType>::commuteHelper(ExprTreeNode* p)
{}
template <typename DataType>
bool ExprTree<DataType>::isEquivalent(const ExprTree& source) const
{
}
template <typename DataType>
bool ExprTree<DataType>::isEquivalentHelper(const ExprTreeNode* x,
const ExprTreeNode* y) const
{}
template <typename DataType>
bool ExprTree<DataType>::isEmpty() const
{
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
}
}
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;
bool isEmpty() 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.
void buildHelper(ExprTreeNode*& p);
void exprHelper(ExprTreeNode* p) const;
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
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 0 // Programming Exercise 1: Logic tree activator
#define LAB8_TEST2 0 // Programming Exercise 2: Commute operation
#define LAB8_TEST3 0 // Programming Exercise 3: isEquivalent operation
Explanation / Answer
test8.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();
//testExpression.expression();
//cout << " = " << testExpression.evaluate() << endl;
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.expression();
//cout << " = " << copyTree.evaluate() << endl;
copyTree.clear();
cout << "Copy cleared: " << endl;
copyTree.showStructure();
}
---------------------------------------------------------------------------
ExpressionTree.cpp
-----------------------------------------------
#include <stdexcept>
#include <iostream>
#include "ExpressionTree.h"
using namespace std;
//--------------------------------------------------------------------
/**
* constructor
*
* Creates an empty expression tree.
*/
template <typename DataType>
ExprTree<DataType>::ExprTree ()
{
/// set root to null
root = NULL;
}
/**
* copy constructor
*
* Initializes the expression tree to be equivalent to the other
* ExprTree object parameter.
* @param source reference to an expression tree to be copied from
*/
template <typename DataType>
ExprTree<DataType>::ExprTree(const ExprTree& source)
{
/// set root to null
root = NULL;
/// use copy helper to set values
copyHelper( root, source.root );
}
/**
* assignment operator
*
* Sets the expression tree to be equivalent to the other ExprTree
* parameter and returns a reference to this object.
* @param source reference to an expression tree to be copied from
* @return ExprTree& reference to this expression tree
*/
template <typename DataType>
ExprTree<DataType>& ExprTree<DataType>::operator=(const ExprTree& source)
{
/// if not same expression trees
if( this != & source )
{
/// clear values
clear();
/// copy values using copy helper
copyHelper( root, source.root );
}
/// return this expression tree, dereferenced
return *this;
}
/**
* destructor
*
* Dellocates (frees) the memory used to store the expression tree.
*/
template <typename DataType>
ExprTree<DataType>::~ExprTree ()
{
/// clear values
clear();
}
/**
* build
*
* Reads an arithmetic expression in prefix form from the keyboard
* and builds the corresponding expression tree.
*/
template <typename DataType>
void ExprTree<DataType>::build ()
{
/// use build helper to build expression tree
buildHelper( root );
}
/**
* expression
*
* Outputs the expression corresponding to the value of the tree
* in fully parenthesized infix form.
*/
template <typename DataType>
void ExprTree<DataType>::expression () const
{
/// if tree is not empty
if( root != NULL )
{
/// use expression helper to output expression
expressionHelper( root );
}
}
/**
* evaluate
*
* Returns the value of the corresponding arithmatic expression.
* @pre The expression tree cannot be empty
* @exception logic_error Throws exception if expression tree is empty.
*/
template <typename DataType>
DataType ExprTree<DataType>::evaluate() const throw (logic_error)
{
/// initialization
DataType answer;
/// if tree is empty
if( root == NULL )
{
/// throw logic error if empty tree
throw logic_error( "Empty tree" );
}
/// if tree is not empty
else
{
/// use evaluate helper to get answer
answer = evaluateHelper( root );
/// return answer
return answer;
}
}
/**
* clear
*
* Removes all of the data items in the expression tree.
*/
template <typename DataType>
void ExprTree<DataType>::clear()
{
/// if tree is not empty
if( root != NULL )
{
/// use clearHelper to delete all values
clearHelper( root );
}
}
/**
* commute
*
* Commutes the operands for every arithmatic operator in the
* expression tree.
*/
template <typename DataType>
void ExprTree<DataType>::commute()
{
/// if tree is not empty
if( root != NULL )
{
/// use commuteHelper to swap values
commuteHelper( root );
}
}
/**
* isEquivalent
*
* Compares the expression tree to another expression tree for equivalence.
* If the two trees are equivalent, then returns true. Otherwise,
* returns false.
*/
template <typename DataType>
bool ExprTree<DataType>::isEquivalent(const ExprTree& source) const
{
// return true if both trees empty
if( root == NULL && source.root == NULL )
{
return true;
}
/// return false is only one trees empty
else if( root == NULL || source.root == NULL )
{
return false;
}
/// otherwise, return bool returned by equivHelper
else
{
return equivHelper( root, source.root );
}
}
/**
* showStructure
*
* Outputs an expression tree with its brances oriented from left
* (root) to right (leaves). The tree output is roated counterclockwise
* ninety degrees from its conventional orientation. If the tree is
* empty, output "Empty tree".
*/
template <typename DataType>
void ExprTree<DataType>::showStructure () const
{
/// if tree is empty
if ( root == NULL )
{
/// print tree is empty
cout << "Empty tree" << endl;
}
/// if tree has values
else
{
/// use showHelper to print structure
cout << endl;
showHelper(root,1);
cout << endl;
}
}
/**
* constructor
*
* Creates an expression tree node.
* @param elem char that holds value to be placed in node
* @param *leftPtr ExprTreeNode pointer to next node to the left
* @param *rightPtr ExprTreeNode pointer to next node to the right
*/
template <typename DataType>
ExprTree<DataType>::ExprTreeNode::ExprTreeNode ( char elem, ExprTreeNode *leftPtr, ExprTreeNode *rightPtr )
{
/// set data members of ExprTreeNode
dataItem = elem;
left = leftPtr;
right = rightPtr;
}
/**
* buildHelper
*
* Recursive helper for the build() function. Creates ptr node and
* subtree whose root node is pointed to by ptr.
* @param ptr ExprTreeNode* to current node
*/
template <typename DataType>
void ExprTree<DataType>::buildHelper( ExprTreeNode* &ptr )
{
/// initialize variables
char val;
/// read in a value
cin >> val;
/// if its not an endline
if( val != ' ' )
{
/// build a new node
ptr = new ExprTreeNode( val, NULL, NULL );
/// if its not a digit
if( !isdigit( val ) )
{
/// build left and right values
buildHelper( ptr -> left );
buildHelper( ptr -> right );
}
}
/// finish building expression tree
return;
}
/**
* evaluateHelper
*
* Recursive helper for the evaluate() function. Calculates the value of
* subtree whose root node is pointed to by ptr.
* @param ptr ExprTreeNode* to current node
* @return DataType answer of arithmatic equation
*/
template <typename DataType>
DataType ExprTree<DataType>::evaluateHelper( ExprTreeNode* ptr ) const
{
/// initialize
DataType leftInt, rightInt;
DataType answer;
/// if data is a digit
if( isdigit( ptr -> dataItem ) )
{
/// return numberical value of answer
answer = (ptr -> dataItem) - '0';
return answer;
}
/// if data is an operator
else
{
/// recursively call evaluate left and right values
leftInt = evaluateHelper( ptr -> left );
rightInt = evaluateHelper( ptr -> right );
/// for each operator, do math
switch( ptr -> dataItem )
{
case '+':
answer = leftInt + rightInt;
break;
case '-':
answer = leftInt - rightInt;
break;
case '*':
answer = leftInt * rightInt;
break;
case '/':
/// divide by zero saves as int
answer = leftInt / rightInt;
break;
}
/// return calculated value
return answer;
}
}
/**
* expressionHelper
*
* Recursive helper for the expression() function. Prints each
* item in subtree whose root node is pointed to by ptr.
* @param ptr ExprTreeNode* to current node
*/
template <typename DataType>
void ExprTree<DataType>::expressionHelper( ExprTreeNode* ptr ) const
{
/// initialize
DataType leftInt, rightInt;
/// if data is digit
if( isdigit( ptr -> dataItem ) )
{
/// print digit
cout << ptr -> dataItem;
}
/// if data is not a digit
else
{
/// for each operator
/// print parentheses and operator and recursive call left and right
switch( ptr -> dataItem )
{
case '+':
cout << '(';
expressionHelper( ptr -> left );
cout << '+';
expressionHelper( ptr -> right );
cout << ')';
break;
case '-':
cout << '(';
expressionHelper( ptr -> left );
cout << '-';
expressionHelper( ptr -> right );
cout << ')';
break;
case '*':
cout << '(';
expressionHelper( ptr -> left );
cout << '*';
expressionHelper( ptr -> right );
cout << ')';
break;
case '/':
cout << '(';
expressionHelper( ptr -> left );
cout << '/';
expressionHelper( ptr -> right );
cout << ')';
break;
}
}
}
/**
* clearHelper
*
* Recursive helper for the clear() function. Deltes each
* item in subtree (bottom to top) whose root node is
* pointed to by ptr. Then deletes ptr (root).
* @param ptr ExprTreeNode* to current node
*/
template <typename DataType>
void ExprTree<DataType>::clearHelper( ExprTreeNode* &ptr )
{
/// if data is a digit
if( isdigit( ptr -> dataItem ) )
{
/// delete node
delete ptr;
/// set to null
ptr = NULL;
}
/// if data has children
else
{
/// clear left and right chilren
clearHelper( ptr -> left );
clearHelper( ptr -> right );
/// delete root
delete ptr;
/// set to null
ptr = NULL;
}
}
/**
* copyHelper
*
* Recursive helper for the copy constructor function. Calls itself
* with values of source until all digits placed.
* @param ptr ExprTreeNode* to current node
* @param sourcePtr ExprTreeNode* to source's current node
*/
template <typename DataType>
void ExprTree<DataType>::copyHelper( ExprTreeNode* &ptr, ExprTreeNode* sourcePtr )
{
/// copy value in source node
ptr = new ExprTreeNode( sourcePtr -> dataItem, NULL, NULL );
/// if its not a digit
if( !isdigit( sourcePtr -> dataItem ) )
{
/// copy left and right values
copyHelper( ptr -> left, sourcePtr -> left );
copyHelper( ptr -> right, sourcePtr -> right );
}
}
/**
* showHelper
*
* 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.
* @param p ExprTreeNode* to current node
* @param level int current level of tree
*/
template <typename DataType>
void ExprTree<DataType>::showHelper( ExprTreeNode* p, int level ) const
{
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
}
}
/**
* commuteHelper
*
* Recursive helper for the commute() function. Calls
* itself to swap each value of subtree until all values swapped.
* @param p ExprTreeNode* to current node
*/
template <typename DataType>
void ExprTree<DataType>::commuteHelper( ExprTreeNode* ptr )
{
/// if digit, return
if( isdigit( ptr -> dataItem ) )
{
return;
}
/// if not digit, swap values and recurse with children
else
{
ExprTreeNode* temp = ptr -> left;
ptr -> left = ptr -> right;
ptr -> right = temp;
commuteHelper( ptr -> right );
commuteHelper( ptr -> left );
}
}
/**
* equivHelper
*
* Recursive helper for the isEquivalent() function. Checks if expression tree
* is equivalent to expression tree in parameters, including commutative property.
* @param ptr ExprTreeNode* to current node
* @param sourcePtr ExprTreeNode* to source's current node
* @return bool flag noting equivalency in this specific call
*/
template <typename DataType>
bool ExprTree<DataType>::equivHelper( ExprTreeNode* ptr, ExprTreeNode* sourcePtr ) const
{
/// set flag to false
bool flag = false;
/// check if equal data
if( ptr -> dataItem == sourcePtr -> dataItem )
{
/// if either is digit
if( isdigit( ptr -> dataItem ) || isdigit( sourcePtr -> dataItem ) )
{
/// return if values the same
flag = ( ptr -> dataItem == sourcePtr -> dataItem );
}
/// if not a digit
else
{
/// call to check children's values and flag if equal
if( equivHelper( ptr -> left, sourcePtr -> left ) &&
equivHelper( ptr -> right, sourcePtr -> right ) )
{
flag = true;
}
/// if operator commutable, check children's values commuted
else if( ptr -> dataItem == '*' || ptr -> dataItem == '+' )
{
if( equivHelper( ptr -> left, sourcePtr -> right ) &&
equivHelper( ptr -> right, sourcePtr -> left ) )
{
flag = true;
}
}
/// if not same children, flag false
else
{
flag = false;
}
}
}
/// return flag value for this call
return flag;
}
---------------------------------------------------------------------------------------------
ExpressionTree.h
----------------------------------------------------------
#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(); // Exercise 2
bool isEquivalent(const ExprTree& source) const; // Exercise 3
// 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
};
void buildHelper( ExprTreeNode* &ptr );
DataType evaluateHelper( ExprTreeNode* ptr ) const;
void expressionHelper( ExprTreeNode* ptr ) const;
void clearHelper( ExprTreeNode* &ptr );
void copyHelper( ExprTreeNode* &ptr, ExprTreeNode* sourcePtr );
void showHelper( ExprTreeNode* ptr, int level ) const;
void commuteHelper( ExprTreeNode* ptr );
bool equivHelper( ExprTreeNode* ptr, ExprTreeNode* sourcePtr ) const;
// Data member
ExprTreeNode *root; // Pointer to the root node
};
#endif // #ifndef EXPRESSIONTREE_H
----------------------------------------------------------------------------------------
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 0 // Programming Exercise 1: Logic tree activator
#define LAB8_TEST2 1 // Programming Exercise 2: Commute operation
#define LAB8_TEST3 1 // Programming Exercise 3: isEquivalent operation
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.