C Program to Create Expression Tree from Postfix Expression

«
»
This is a C Program to construxt and solve expression tree for postfix expression. A binary expression tree is a specific application of a binary tree to evaluate certain expressions.

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.

  1. #include<stdio.h>
  2. #include<conio.h>
  3. #include<malloc.h>
  4. #include<stdlib.h>
  5. #include<string.h>
  6.  
  7. struct tree {
  8.     char data;
  9.     struct tree *left, *right;
  10. };
  11.  
  12. int top = -1;
  13. struct tree *stack[20];
  14. struct tree *node;
  15.  
  16. void push(struct tree* node) {
  17.     stack[++top] = node;
  18. }
  19.  
  20. struct tree * pop() {
  21.     return (stack[top--]);
  22. }
  23.  
  24. int cal(struct tree *node) {
  25.     int ch;
  26.     ch = check(node->data);
  27.     if (ch == 1)
  28.         return node->data - 48;
  29.     else if (ch == 2) {
  30.         if (node->data == '+')
  31.             return cal(node->left) + cal(node->right);
  32.         if (node->data == '-')
  33.             return cal(node->left) - cal(node->right);
  34.         if (node->data == '*')
  35.             return cal(node->left) * cal(node->right);
  36.         if (node->data == '/')
  37.             return cal(node->left) / cal(node->right);
  38.     }
  39. }
  40.  
  41. void inorder(struct tree *node) {
  42.     if (node != NULL) {
  43.         inorder(node->left);
  44.         printf("%c", node->data);
  45.         inorder(node->right);
  46.     }
  47. }
  48.  
  49. int check(char ch) {
  50.     if (ch == '+' || ch == '-' || ch == '/' || ch == '*')
  51.         return 2;
  52.     else
  53.         return 1;
  54. }
  55.  
  56. void operand(char b) {
  57.     node = (struct tree*) malloc(sizeof(struct tree));
  58.     node->data = b;
  59.     node->left = NULL;
  60.     node->right = NULL;
  61.     push(node);
  62. }
  63.  
  64. void operators(char a) {
  65.     node = (struct tree*) malloc(sizeof(struct tree));
  66.     node->data = a;
  67.     node->right = pop();
  68.     node->left = pop();
  69.     push(node);
  70. }
  71.  
  72. int main(int argc, char **argv) {
  73.     int i, p, k, ans;
  74.     char s[20];
  75.     printf("Enter the expression in postfix form \n");
  76.     fflush(stdin);
  77.     gets(s);
  78.     k = strlen(s);
  79.     i = 0;
  80.     for (i = 0; s[i] != '\0'; i++) {
  81.         p = check(s[i]);
  82.         if (p == 1)
  83.             operand(s[i]);
  84.         else if (p == 2)
  85.             operators(s[i]);
  86.     }
  87.     ans = cal(stack[top]);
  88.     printf("\nThe value of the postfix expression you entered is %d\n", ans);
  89.     printf("\nThe inorder traversal of the tree is \n");
  90.     inorder(stack[top]);
  91.     return 0;
  92. }

Output:

advertisement
$ gcc PostfixExpressionTree.c
$ ./a.out
 
Enter the expression in postfix form
234*+
 
The value if the postfix expression you entered is 14
 
The inorder traveresal of the tree is
2+3*4

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.