- Implement a tree which constructs an expression tree from the prefix form of a
ID: 3733329 • Letter: #
Question
- 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 <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
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
}
}
test8.cpp
#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();
}
Explanation / Answer
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
class ExpressionTree
{
public:
char data;
ExpressionTree *left, *right;
ExpressionTree(char data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class StackNode
{
public:
ExpressionTree *ExpressionTree;
StackNode *next;
StackNode(ExpressionTree *ExpressionTree)
{
this->ExpressionTree = ExpressionTree;
next = NULL;
}
};
class ExpressionTree
{
private:
StackNode *top;
public:
ExpressionTree()
{
top = NULL;
}
void clear()
{
top = NULL;
}
void push(ExpressionTree *ptr)
{
if (top == NULL)
top = new StackNode(ptr);
else
{
StackNode *nptr = new StackNode(ptr);
nptr->next = top;
top = nptr;
}
}
ExpressionTree *pop()
{
if (top == NULL)
{
cout<<"Underflow"<<endl;
}
else
{
ExpressionTree *ptr = top->ExpressionTree;
top = top->next;
return ptr;
}
}
ExpressionTree *peek()
{
return top->ExpressionTree;
}
void insert(char val)
{
if (isDigit(val))
{
ExpressionTree *nptr = new ExpressionTree(val);
push(nptr);
}
else if (isOperator(val))
{
ExpressionTree *nptr = new ExpressionTree(val);
nptr->left = pop();
nptr->right = pop();
push(nptr);
}
else
{
cout<<"Invalid Expression"<<endl;
return;
}
}
bool isDigit(char ch)
{
return ch >= '0' && ch <= '9';
}
bool isOperator(char ch)
{
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
int toDigit(char ch)
{
return ch - '0';
}
void build(string eqn)
{
for (int i = eqn.length() - 1; i >= 0; i--)
insert(eqn[i]);
}
double evaluate()
{
return evaluate(peek());
}
double evaluate(ExpressionTree *ptr)
{
if (ptr->left == NULL && ptr->right == NULL)
return toDigit(ptr->data);
else
{
double result = 0.0;
double left = evaluate(ptr->left);
double right = evaluate(ptr->right);
char op = ptr->data;
switch (op)
{
case '+':
result = left + right;
break;
case '-':
result = left - right;
break;
case '*':
result = left * right;
break;
case '/':
result = left / right;
break;
default:
result = left + right;
break;
}
return result;
}
}
void postfix()
{
postOrder(peek());
}
void postOrder(ExpressionTree *ptr)
{
if (ptr != NULL)
{
postOrder(ptr->left);
postOrder(ptr->right);
cout<<ptr->data;
}
}
void infix()
{
inOrder(peek());
}
void inOrder(ExpressionTree *ptr)
{
if (ptr != NULL)
{
inOrder(ptr->left);
cout<<ptr->data;
inOrder(ptr->right);
}
}
void prefix()
{
preOrder(peek());
}
void preOrder(ExpressionTree *ptr)
{
if (ptr != NULL)
{
cout<<ptr->data;
preOrder(ptr->left);
preOrder(ptr->right);
}
}
};
int main()
{
string s;
cout<<"Expression Tree Test"<<endl;
ExpressionTree et;
cout<<" Enter equation in Prefix form: ";
cin>>s;
et.build(s);
cout<<" Prefix : ";
et.prefix();
cout<<" Infix : ";
et.infix();
cout<<" Postfix : ";
et.postfix();
cout<<" Evaluated Result : "<<et.evaluate();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.