C++ Program to Construct an Expression Tree for a Postfix Expression
Posted by Superadmin on December 07 2015 01:37:39

---

This is a C++ Program to create an expression tree and print the various traversals using postfix expression.
Here is source code of the C++ Program to Construct an Expression Tree for a Postfix Expression. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

#include <iostream>
#include <conio.h>

using namespace std;

struct node
{
char data;
node *left;
node *right;
};

char postfix[35];
int top = -1;
node *arr[35];

int r(char inputchar)
{ //for checking symbol is operand or operator
if (inputchar == '+' || inputchar == '-' || inputchar == '*' || inputchar
== '/')
return (-1);
else if (inputchar >= 'a' || inputchar <= 'z')
return (1);
else if (inputchar >= 'A' || inputchar <= 'Z')
return (1);
else
return (-99); //for error
}

//it is used for inseting an single element in//a tree, i.e. is pushing of single element.
void push(node *tree)
{
top++;
arr[top] = tree;
}

node *pop()
{
top--;
return (arr[top + 1]);
}

void create_expr_tree(char *suffix)
{
char symbol;
node *newl, *ptr1, *ptr2;
int flag; //flag=-1 when operator and flag=1 when operand
symbol = suffix[0]; //Read the first symbol from the postfix expr.
for (int i = 1; symbol != NULL; i++)
{ //continue till end of the expr.
flag = r(symbol); //check symbol is operand or operator.
if (flag == 1)//if symbol is operand.
{
newl = new node;
newl->data = symbol;
newl->left = NULL;
newl->right = NULL;
push(newl);
}
else
{ //If the symbol is operator//pop two top elements.
ptr1 = pop();
ptr2 = pop();
newl = new node;
newl->data = symbol;
newl->left = ptr2;
newl->right = ptr1;
push(newl);
}
symbol = suffix[i];
}
}

void preOrder(node *tree)
{
if (tree != NULL)
{
cout << tree->data;
preOrder(tree->left);
preOrder(tree->right);
}
}

void inOrder(node *tree)
{
if (tree != NULL)
{
inOrder(tree->left);
cout << tree->data;
inOrder(tree->right);
}
}

void postOrder(node *tree)
{
if (tree != NULL)
{
postOrder(tree->left);
postOrder(tree->right);
cout << tree->data;
}
}

int main(int argc, char **argv)
{
cout << "Enter Postfix Expression : ";
cin >> postfix;

//Creation of Expression Tree
create_expr_tree(postfix);

//Traversal Operation on expression tree
cout << "\nIn-Order Traversal : ";
inOrder(arr[0]);

cout << "\nPre-Order Traversal : ";
preOrder(arr[0]);

cout << "\nPost-Order Traversal : ";
postOrder(arr[0]);
return 0;
}


Output:

$ g++ ExpressionTreePostfix.cpp
$ a.out

Enter Postfix Expression : 32+5*

In-Order Traversal : 3+2*5
Pre-Order Traversal : *+325
Post-Order Traversal : 32+5*

------------------
(program exited with code: 0)
Press return to continue