Expression Trees This project deals with a simple kind of expression tree, where
ID: 3845644 • Letter: E
Question
Expression Trees
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. Also include a recursive function to “evaluate”
a non-empty expression tree using these rules:
(a) If the tree has only one node (which must be
a leaf), then the evaluation of the tree returns the real
number that is the node’s entry;
(b) If the tree has more than one node, and the
root contains +, then first evaluate the left subtree,
then evaluate the right subtree, and add the results.
If the root contains *, then evaluate the two subtrees
and multiply the results.
// FILE: express.h
// CLASS PROVIDED: ExpressionTree
// This class provides only NONEMPTY expression trees
// from Project 1 of Chapter 10 in first edition of
// "Data Structures and Other Objects Using C++".
// This current version just slightly modified for CS 24
// by cmc, 11/17/2016.
//
// CONSTRUCTORS for the ExpressionTree class:
// ExpressionTree(double value = 0.0)
// Postcondition: The ExpressionTree has one leaf node with the specified
// value. The default argument is 0.0.
//
// CONST Member Functions for the ExpressionTree class:
// double evaluate( ) const
// Postcondition: The return value is the value of the expression tree.
//
// void printPre() const;
// Postcondition: The expression is printed in prefix form to standard output.
//
// void printPost() const;
// Postcondition: The expression is printed in postfix form to standard output.
//
// void printIn() const;
// Postcondition: The expression is printed in infix form to standard output,
// with add operations enclosed in parentheses.
//
// NONMEMBER FUNCTIONS for the ExpressionTree class:
// ExpressionTree operator +(const ExpressionTree& e1, const ExpressionTree& e2)
// Postcondition: The ExpressionTree returned has '+' at the root, e1 as the
// left subtree, and e2 as the right subtree.
//
// ExpressionTree operator *(const ExpressionTree& e1, const ExpressionTree& e2)
// Postcondition: The ExpressionTree returned has '*' at the root, e1 as the
// left subtree, and e2 as the right subtree.
//
// VALUE SEMANTICS for the ExpressionTree class:
// Assignments and the copy constructor may be used with ExpressionTree
// objects.
#ifndef EXPRESS_H
#define EXPRESS_H
#include <cstdlib> // Provides NULL
class ExpressionTree
{
public:
// CONSTRUCTORS and DESTRUCTOR
ExpressionTree(double value = 0.0);
ExpressionTree(const ExpressionTree& source);
~ExpressionTree( );
// ASSIGNMENT OPERATOR
ExpressionTree& operator =(const ExpressionTree& source);
// CONSTANT MEMBER FUNCTIONS
double evaluate( ) const;
void printPre() const;
void printPost() const;
void printIn() const;
// NONMEMBER FUNCTIONS FOR BUILDING BIGGER EXPRESSION TREES:
friend
ExpressionTree operator +(const ExpressionTree& e1, const ExpressionTree& e2);
friend
ExpressionTree operator *(const ExpressionTree& e1, const ExpressionTree& e2);
private:
double data; // Used for leaf nodes only.
char operation; // Used for non-leaf nodes only.
ExpressionTree *left; // Will be NULL for a leaf.
ExpressionTree *right; // Will be NULL for a leaf.
};
#endif
Explanation / Answer
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
/** class TreeNode **/
class TreeNode
{
public:
char data;
TreeNode *left, *right;
/** constructor **/
TreeNode(char data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
/** class StackNode **/
class StackNode
{
public:
TreeNode *treeNode;
StackNode *next;
/** constructor **/
StackNode(TreeNode *treeNode)
{
this->treeNode = treeNode;
next = NULL;
}
};
class ExpressionTree
{
private:
StackNode *top;
public:
/** constructor **/
ExpressionTree()
{
top = NULL;
}
/** function to clear tree **/
void clear()
{
top = NULL;
}
/** function to push a node **/
void push(TreeNode *ptr)
{
if (top == NULL)
top = new StackNode(ptr);
else
{
StackNode *nptr = new StackNode(ptr);
nptr->next = top;
top = nptr;
}
}
/** function to pop a node **/
TreeNode *pop()
{
if (top == NULL)
{
cout<<"Underflow"<<endl;
}
else
{
TreeNode *ptr = top->treeNode;
top = top->next;
return ptr;
}
}
/** function to get top node **/
TreeNode *peek()
{
return top->treeNode;
}
/** function to insert character **/
void insert(char val)
{
if (isDigit(val))
{
TreeNode *nptr = new TreeNode(val);
push(nptr);
}
else if (isOperator(val))
{
TreeNode *nptr = new TreeNode(val);
nptr->left = pop();
nptr->right = pop();
push(nptr);
}
else
{
cout<<"Invalid Expression"<<endl;
return;
}
}
/** function to check if digit **/
bool isDigit(char ch)
{
return ch >= '0' && ch <= '9';
}
/** function to check if operator **/
bool isOperator(char ch)
{
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
/** function to convert character to digit **/
int toDigit(char ch)
{
return ch - '0';
}
/** function to build tree from input */
void buildTree(string eqn)
{
for (int i = eqn.length() - 1; i >= 0; i--)
insert(eqn[i]);
}
/** function to evaluate tree */
double evaluate()
{
return evaluate(peek());
}
/** function to evaluate tree */
double evaluate(TreeNode *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;
}
}
/** function to get postfix expression */
void postfix()
{
postOrder(peek());
}
/** post order traversal */
void postOrder(TreeNode *ptr)
{
if (ptr != NULL)
{
postOrder(ptr->left);
postOrder(ptr->right);
cout<<ptr->data;
}
}
/** function to get infix expression */
void infix()
{
inOrder(peek());
}
/** in order traversal */
void inOrder(TreeNode *ptr)
{
if (ptr != NULL)
{
inOrder(ptr->left);
cout<<ptr->data;
inOrder(ptr->right);
}
}
/** function to get prefix expression */
void prefix()
{
preOrder(peek());
}
/** pre order traversal */
void preOrder(TreeNode *ptr)
{
if (ptr != NULL)
{
cout<<ptr->data;
preOrder(ptr->left);
preOrder(ptr->right);
}
}
};
/** Main Contains menu **/
int main()
{
string s;
cout<<"Expression Tree Test"<<endl;
ExpressionTree et;
cout<<" Enter equation in Prefix form: ";
cin>>s;
et.buildTree(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.