C++ Program to Implement Expression Tree Algorithm

This C++ program, implements the expression tree algorithm which consists of operands as terminal nodes and operators as root or sub root nodes. Here is the source code of the C++ program which takes the prefix expression as an input and generates the corresponding expression tree traversed in postorder. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is also shown below.
C++ Program to Implement Expression Tree Algorithm



/*
* C++ Program to Implement Expression Tree Algorithm
*/
#include <iostream>
#include <conio.h>
using namespace std;
struct tree
{
char data;
tree *l, *r;
}*root = NULL, *p = NULL, *t = NULL, *y = NULL;
struct node
{
tree *pt;
node *next;
}*top = NULL, *q = NULL, *np = NULL;
void push(tree *ptr)
{
np = new node;
np->pt = ptr;
np->next = NULL;
if (top == NULL)
{
top = np;
}
else
{
q = top;
top = np;
np->next = q;
}
}
tree *pop()
{
if (top == NULL)
{
cout<<"underflown";
}
else
{
q = top;
top = top->next;
return(q->pt);
delete(q);
}
}
void oprnd_str(char val)
{
if (val >= 48 && val <= 57)
{
t = new tree;
t->data = val;
t->l = NULL;
t->r = NULL;
push(t);
}
else if (val >= 42 && val <= 47)
{
p = new tree;
p->data = val;
p->l = pop();
p->r = pop();
push(p);
}
}
char pstorder(tree *w)
{
if (w != NULL)
{
pstorder(w->l);
pstorder(w->r);
cout<<w->data;
}
}
int main()
{
char a[15];
int i;
int j = -1;
cout<<"enter the value of character stringn";
cin>>a;
i = strlen(a);
while (i >= 0)
{
i--;
oprnd_str(a[i]);
}
cout<<"displaying in postordern";
pstorder(pop());
getch();
}


Output:
enter the value of character string
-+-5/763*48
displaying in postorder
576/-3+48*-


Post a Comment