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.

```
#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.

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

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement Interval Tree

» Next - C Program to Implement Range Tree

Related Posts:

Recommended Articles: