- Implement a tree which constructs an expression tree from the prefix form of a
ID: 3734009 • 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 #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 << " "; 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(); }
Explanation / Answer
//test.cpp
#include <iostream>
#include <stdexcept>
using namespace std;
#include "ExpressionTree.cpp"
#include "config.h"
// Function prototype
template<typename T>
void dummy(ExprTree<T> copyTree); // copyTree is passed by value
int main() {
#if !LAB8_TEST1 || LAB8_TEST2 || LAB8_TEST3
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;
}
// Dummy routine that is passed an expression tree using call by
// value. Outputs copyTree and clears it.
template<typename T>
void dummy(ExprTree<T> copyTree) {
cout << endl << "Copy of tree: " << endl;
copyTree.showStructure();
copyTree.clear();
cout << "Copy cleared: " << endl;
copyTree.showStructure();
}
--------------------------------------------------------------------------------------
//ExpressionTree.cpp
#include "ExpressionTree.h"
template<typename T>
ExprTree<T>::ExprTreeNode::ExprTreeNode(char elem, ExprTreeNode *leftPtr, ExprTreeNode *rightPtr) {
dataItem = elem;
left = leftPtr;
right = rightPtr;
}
template<typename T>
ExprTree<T>::ExprTree() {
root = 0;
}
template<typename T>
ExprTree<T>::ExprTree(const ExprTree &source) {
copyHelper(root, source.root);
}
template<typename T>
ExprTree<T>&ExprTree<T>::operator=(const ExprTree &source) {
clearHelper(root);
copyHelper(root, source->root);
}
template<typename T>
void ExprTree<T>::copyHelper(ExprTreeNode* &to, const ExprTreeNode *from) {
if (from == 0) { return; }
to = new ExprTreeNode(from->dataItem, 0, 0);
copyHelper(to->left, from->left);
copyHelper(to->right, from->right);
}
template<typename T>
ExprTree<T>::~ExprTree() {
clearHelper(root);
}
template<typename T>
void ExprTree<T>::build() {
string str;
getline(cin, str);
buildHelper(root, str);
}
template<typename T>
void ExprTree<T>::buildHelper(ExprTreeNode * &p, string &str) {
if (str.empty()) { return; }
if (str[0] == ' ') {
return buildHelper(p, str.erase(0, 1));
}
p = new ExprTreeNode(str[0], 0, 0);
if (is_same<T, bool>::value && (str[0] == '0' || str[0] == '1')) { return; }
if (47 < static_cast<int>(str[0]) && static_cast<int>(str[0]) < 58) { return; }
buildHelper(p->left, str.erase(0, 1));
buildHelper(p->right, str.erase(0, 1));
}
template<typename T>
bool ExprTree<T>::isOperator(const ExprTreeNode *p) const {
if (p == 0) return false;
switch (p->dataItem) {
case '+':
case '-':
case '*':
case '/':
return true;
default:
return false;
}
}
template<typename T>
void ExprTree<T>::expression() const {
exprHelper(root);
}
template<typename T>
void ExprTree<T>::exprHelper(ExprTreeNode *p) const {
if (p == 0) return;
if (!p->left && !p->right) {
cout << p->dataItem;
return;
}
if (is_same<T, bool>::value && p->dataItem == '-' && !p->right) {
cout << "-" << p->left->dataItem;
return;
}
if (!isOperator(p->left) || !isOperator(p->right)) {
cout << "(";
}
exprHelper(p->left);
if (isOperator(p)) {
cout << " " << p->dataItem << " ";
}
else {
cout << p->dataItem;
}
exprHelper(p->right);
if (!isOperator(p->left) || !isOperator(p->right)) {
cout << ")";
}
}
template<typename T>
T ExprTree<T>::evaluate() const {
if (!root) throw logic_error("Tree is empty");
return evalHelper(root);
}
template<typename T>
T ExprTree<T>::evalHelper(ExprTreeNode *p) const {
switch (p->dataItem) {
case '+':
return is_same<T, bool>::value
? evalHelper(p->left) || evalHelper(p->right)
: evalHelper(p->left) + evalHelper(p->right);
case '-':
return is_same<T, bool>::value
? evalHelper(p->left) && ! evalHelper(p->right)
: evalHelper(p->left) - evalHelper(p->right);
case '*':
return is_same<T, bool>::value
? evalHelper(p->left) && evalHelper(p->right)
: evalHelper(p->left) * evalHelper(p->right);
case '/':
if (is_same<T, bool>::value) {
throw logic_error("Invalid operator for type bool");
}
return evalHelper(p->left) / evalHelper(p->right);
default:
return is_same<T, bool>::value
? p->dataItem == '1'
: static_cast<T>(p->dataItem) - 48;
}
}
template<typename T>
void ExprTree<T>::clear() {
clearHelper(root);
}
template<typename T>
void ExprTree<T>::clearHelper(ExprTreeNode * &p) {
if (p == 0) return;
clearHelper(p->left);
clearHelper(p->right);
p = 0;
}
template<typename T>
void ExprTree<T>::commute() {
commuteHelper(root);
}
template<typename T>
void ExprTree<T>::commuteHelper(ExprTreeNode *p) {
if (p == 0) return;
ExprTreeNode *left = p->left;
p->left = p->right;
p->right = left;
commuteHelper(p->left);
commuteHelper(p->right);
}
template<typename T>
bool ExprTree<T>::isEquivalent(const ExprTree &source) const {
return true;
}
template<typename T>
bool ExprTree<T>::isEquivalentHelper(const ExprTreeNode *x, const ExprTreeNode *y) const { return true; }
template<typename T>
bool ExprTree<T>::isEmpty() const {
return false;
}
// Outputs an expression tree.
template<typename T>
void ExprTree<T>::showStructure() const {
// 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;
}
}
// Recursive helper for the showStructure() function.
template<typename T>
void ExprTree<T>::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
}
}
--------------------------------------------------------------------
//ExpressionTree.h
#ifndef EXPRESSIONTREE_H
#define EXPRESSIONTREE_H
#include <stdexcept>
#include <iostream>
#include <string>
#include <type_traits>
using namespace std;
template<typename T>
class ExprTree {
public:
// Constructor
ExprTree();
ExprTree(const ExprTree &source);
// Destructor
~ExprTree();
ExprTree& operator=(const ExprTree &source);
// Expression tree manipulation operations
void build();
void expression() const;
T evaluate() const;
void clear(); // Clear tree
void commute();
bool isEquivalent(const ExprTree &source) const;
bool isEmpty() const;
// Output the tree structure
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
ExprTreeNode *right; // Pointer to the right child
};
// Recursive helper functions for the public member functions
void buildHelper(ExprTreeNode* &p, string &str);
void exprHelper(ExprTreeNode *p) const;
T evalHelper(ExprTreeNode *p) const;
void clearHelper(ExprTreeNode *&p);
void showHelper(ExprTreeNode *p, int level) const;
void copyHelper(ExprTreeNode* &to, const ExprTreeNode *from);
void commuteHelper(ExprTreeNode *p);
bool isEquivalentHelper(const ExprTreeNode *p, const ExprTreeNode *q) const;
bool isOperator(const ExprTreeNode *p) const;
// Data member
ExprTreeNode *root; // Pointer to the root node
};
#endif // #ifndef EXPRESSIONTREE_H
------------------------------------------------
//Config.h
#define LAB8_TEST1 0
#define LAB8_TEST2 1
#define LAB8_TEST3 0
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.