Question: - implement the expression tree adt using c++ programming - implement the Expression Tree ADT (80 points) - implement the following operations: - constructor, copy
- implement the expression tree adt using c++ programming
- implement the Expression Tree ADT (80 points)
- implement the following operations:
- constructor, copy constructor, assignment operator, destructor
- build, expression, evaluate
- clear
#include "ExpressionTree.h"
template
ExprTree
{
}
template
ExprTree
{
}
template
ExprTree
{
}
template
ExprTree
{
}
template
void ExprTree
{}
template
ExprTree
{
}
template
void ExprTree
{
}
#include ExpressionTree.h
template <>
void ExprTree
{}
template <>
void ExprTree
{}
template
void ExprTree
{
}
template
void ExprTree
{}
template
DataType ExprTree
{
DataType temp;
return temp;
}
template <>
float ExprTree
{
float temp;
return temp;
}
template <>
bool ExprTree
{
bool temp;
return temp;
}
template
void ExprTree
{
}
template
void ExprTree
{}
template
void ExprTree
{
}
template
void ExprTree
{}
template
bool ExprTree
{
}
template
bool ExprTree
const ExprTreeNode* y) const
{}
template
bool ExprTree
{
return false;
}
template
void ExprTree
// 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
void ExprTree
// 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 << "\t";
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
}
}
#Include "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
#include
using namespace std;
template
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
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help