Expression Trees This project deals with a simple kind of expression tree, where

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

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.