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.
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
struct tree {
char data;
struct tree *left, *right;
};
int top = -1;
struct tree *stack[20];
struct tree *node;
void push(struct tree* node) {
stack[++top] = node;
}
struct tree * pop() {
return (stack[top--]);
}
int cal(struct tree *node) {
int ch;
ch = check(node->data);
if (ch == 1)
return node->data - 48;
else if (ch == 2) {
if (node->data == '+')
return cal(node->left) + cal(node->right);
if (node->data == '-')
return cal(node->left) - cal(node->right);
if (node->data == '*')
return cal(node->left) * cal(node->right);
if (node->data == '/')
return cal(node->left) / cal(node->right);
}
}
void inorder(struct tree *node) {
if (node != NULL) {
inorder(node->left);
printf("%c", node->data);
inorder(node->right);
}
}
int check(char ch) {
if (ch == '+' || ch == '-' || ch == '/' || ch == '*')
return 2;
else
return 1;
}
void operand(char b) {
node = (struct tree*) malloc(sizeof(struct tree));
node->data = b;
node->left = NULL;
node->right = NULL;
push(node);
}
void operators(char a) {
node = (struct tree*) malloc(sizeof(struct tree));
node->data = a;
node->right = pop();
node->left = pop();
push(node);
}
int main(int argc, char **argv) {
int i, p, k, ans;
char s[20];
printf("Enter the expression in postfix form \n");
fflush(stdin);
gets(s);
k = strlen(s);
i = 0;
for (i = 0; s[i] != '\0'; i++) {
p = check(s[i]);
if (p == 1)
operand(s[i]);
else if (p == 2)
operators(s[i]);
}
ans = cal(stack[top]);
printf("\nThe value of the postfix expression you entered is %d\n", ans);
printf("\nThe inorder traversal of the tree is \n");
inorder(stack[top]);
return 0;
}
Output:
$ 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.
advertisement
advertisement
Here’s the list of Best Books in C Programming, Data Structures and Algorithms.
Related Posts:
- Practice Design & Analysis of Algorithms MCQ
- Check Data Structure Books
- Check Computer Science Books
- Check Programming Books
- Practice Programming MCQs