This project deals with a simple kind of expression tree, where there are two kinds of nodes:

(a) Leaf nodes, which contain a real number as their entry;

(b) Nonleaf nodes, which contain either the character + or the character * as their entry, and have exactly two children.

For this project, implement a class for expression trees, including operations for building expression trees.

Include a private data member and public accessor method (get_root) for the root pointer.

The expressionTree class should have a default constructor to create an empty binary tree and a parameterized constructor to create the binary expression tree from a string parameter containing a valid postfix expression: expressionTree(string&);

Each node of the binary expressionTree can contain either a real number or character value in addition to the left and right subtree pointers. Use the following structure definition to represent this node:

struct expTreeNode { double number; char op; expTreeNode* left_field; expTreeNode* right_field; };

Also include a recursive function to evaluate a non-empty expression with +,-,*,/ for this implementation file:

#include "expressionTree.h"

#include

#include

#include

#include

using namespace std;

// recursively displays binary expression tree

void expTreePrint(const expTreeNode* node_ptr, int depth = 5) {

cout << setw(4 * depth) << ""; // indentation

if (node_ptr == nullptr) {

// fallen off the tree

cout << "[Empty]" << std::endl;

}

else if (node_ptr->left_field == nullptr) {

// a leaf with numeric data

cout << node_ptr->number;

cout << " [leaf]" << std::endl;

}

else {

// a nonleaf with operator

cout << node_ptr->op << std::endl;

expTreePrint(node_ptr->right_field, depth + 1);

expTreePrint(node_ptr->left_field, depth + 1);

}

}

// testing function

int main() {

// create testcases

string testCases[] = { ".5 .25 / ",

"2.5 3.7 + 8.5 * ", "5 3.1 2 * + 4 - 5 + ",

"25 347.8 5 * + 5 / ", "2 3 / " };

double testResults[] = { 2, 52.7, 12.2, 352.8, 0.666667 };

int numTests = sizeof(testResults) / sizeof(double);

// loop for all test cases

for (int index = 0; index < numTests; ++index) {

expressionTree *expTree = new expressionTree(testCases[index]);

// display binary tree

expTreePrint(expTree->get_root());

cout << "Postfix expression: " << testCases[index]

<< " \t==> evaluates to " << evaluate(expTree->get_root())

<< " \t==> correct answer is " << testResults[index] << endl;

// release memory

delete expTree;

}

return EXIT_SUCCESS;

}