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
*/
#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<<"underflow\n";
}
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 string\n";
cin>>a;
i = strlen(a);
while (i >= 0)
{
i--;
oprnd_str(a[i]);
}
cout<<"displaying in postorder\n";
pstorder(pop());
getch();
}
advertisement
Output: enter the value of character string -+-5/763*48 displaying in postorder 576/-3+48*-
Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!