- Implement a tree which constructs an expression tree from the prefix form of an arithmetic expression.

Example of the prefix form: * + 1 3 6 4

Example of the infix form: (1 + 3) * (6 - 4)

Functions to implement:

- build() - builds corresponding expression tree: (25 pts)

- expression() - converts and outputs prefix form into infix form: (25 pts)

- evaluate() - returns the value of corresponding expression tree: (25 pts)

- Other functions (constructor, copy constructor, desctructor, clear()) (25 pts)

ExpressionTree.h

#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

ExpressionTree.cpp

#include "ExpressionTree.h"

template

ExprTree::ExprTreeNode::ExprTreeNode ( char elem, ExprTreeNode *leftPtr, ExprTreeNode *rightPtr )

{

}

template

ExprTree::ExprTree ()

{

}

template

ExprTree::ExprTree(const ExprTree& source)

{

}

template

ExprTree& ExprTree::operator=(const ExprTree& source)

{

}

template

void ExprTree::copyHelper(ExprTreeNode *&p)

{}

template

ExprTree::~ExprTree ()

{

}

template

void ExprTree::build ()

{

}

template <>

void ExprTree::buildHelper(ExprTreeNode*& p)

{}

template <>

void ExprTree::buildHelper(ExprTreeNode*& p)

{}

template

void ExprTree::expression () const

{

}

template

void ExprTree::exprHelper(ExprTreeNode* p) const

{}

template

DataType ExprTree::evaluate() const throw (logic_error)

{

DataType temp;

return temp;

}

template <>

float ExprTree::evalHelper(ExprTreeNode* p) const

{

float temp;

return temp;

}

template <>

bool ExprTree::evalHelper(ExprTreeNode* p) const

{

bool temp;

return temp;

}

template

void ExprTree::clear ()

{

}

template

void ExprTree::clearHelper(ExprTreeNode *p)

{}

template

void ExprTree::commute()

{

}

template

void ExprTree::commuteHelper(ExprTreeNode* p)

{}

template

bool ExprTree::isEquivalent(const ExprTree& source) const

{

}

template

bool ExprTree::isEquivalentHelper(const ExprTreeNode* x,

const ExprTreeNode* y) const

{}

template

bool ExprTree::isEmpty() const

{

return false;

}

template

void ExprTree::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

void ExprTree::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 << "\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

}

}

test8.cpp

#include

#include

using namespace std;

//#include "ExprTree.cpp"

#include "ExpressionTree.cpp"

#include "config.h"

//--------------------------------------------------------------------

// Function prototype

template

void dummy ( ExprTree 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 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 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 same = testExpression;

cout << "same is equal (tests copy constructor) ? ";

cout << (same.isEquivalent(testExpression) ? "Yes" : "No") << endl;

ExprTree empty;

cout << "empty is equal? ";

cout << (empty.isEquivalent(testExpression) ? "Yes" : "No") << endl;

ExprTree 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

void dummy ( ExprTree 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();

}