C++ Program to Construct an Expression Tree for a Given Prefix Expression

This C++ program, using recursion, evaluates a Prefix Expression in an Expression Tree. A binary expression tree is a specific application of a binary tree to evaluate certain expressions.
Here is the source code of the C++ program to evaluate a Prefix Expression. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
* C++ Program to Construct an Expression Tree for a Given Prefix Expression
*/
#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"< 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<<"\nEnter equation in Prefix form: ";
cin>>s;
et.buildTree(s);
cout<<"\nPrefix : ";
et.prefix();
cout<<"\n\nInfix : ";
et.infix();
cout<<"\n\nPostfix : ";
et.postfix();
cout<<"\n\nEvaluated Result : "<< et.evaluate();
return 0;
}

Output

$ g++ prefix.cpp
$ a.out

Expression Tree Test

Enter equation in Prefix form: +-+7*/935/82*/625

Prefix : +-+7*/935/82*/625

Infix : 7+9/3*5-8/2+6/2*5

Postfix : 793/5*+82/-62/5*+

Evaluated Result : 33