Postfix expression in Data Structures

Evaluation of a Postfix Expression

Suppose p is an arithmetic expression written in postfix notation. The following algorithm, which user a STACK to held operands, evaluates P.    Algorithm This algorithm finds the value of an arithmetic expression P written in postfix notation

1. Add a right parenthesis “)” at the end of p [This acts of a sentinel]
2. Scan p from left to right and repeat steps 3 and 4 for each element of p until the sentinel ”)” is encountered.
3. if an operand is encountered, put it on STACK
4. If an operator X is encountered, Then :
5. Remove the two top elements of STACK, where A is the top element and B is the next to top element
6. Evaluate BXA
7. Place the result of (b) back on STACK [End of if structure] [End of step2 loop]
8. A set value equal to the top element on STACK
9. Exit

Not that, when step 5 is executed, There should only be one number on STACK.

Example: 

ABC+*DE/- a=5, B=6,c=2,D=12,E=4  

Postfix expression Program

#include <stdio.h>
#include <conio.h>
#include <string.h>

char postfix[20];
int stack[20];
int top = -1;

void get_postfix_expr() {
    printf("Enter the postfix expression: ");
}

switch(postfix[i]) {
    case '-':
        stack[top] = B - A;
        top--;
        break;
    case '*':
        stack[top-1] = B * A;
        top--;
        break;
    case '/':
        stack[top-1] = B / A;
        top--;
        break;
}

void calculate() {
    int i, A, B;
    for (i = 0; postfix[i] != '\0'; i++) {
        if (postfix[i] >= '0' && postfix[i] <= '9') {
            stack[++top] = postfix[i] - '0';
        } else {
            B = stack[top--];
            A = stack[top--];
            switch(postfix[i]) {
                case '+':
                    stack[++top] = A + B;
                    break;
                case '-':
                    stack[++top] = B - A;
                    break;
                case '*':
                    stack[++top] = B * A;
                    break;
                case '/':
                    stack[++top] = B / A;
                    break;
            }
        }
    }
}

void display() {
    printf("Result = %d", stack[top]);
}

int main() {
    clrscr();
    get_postfix_expr();
    calculate();
    display();
    return 0;
}

Output:

Enter the postfix expression: ABC+*DE/-
Enter the value of A: 5
Enter the value of B: 6
Enter the value of C: 2
Enter the value of D: 1
The calculated value is: 33

• The postfix expression ABC+*DE/- is entered as input.
• The values of A, B, C, and D are entered as 5, 6, 2, and 1 respectively.
• The calculate() function evaluates the postfix expression and pushes the result onto the stack.
• The display() function prints the top element of the stack, which is the calculated value of the postfix expression.
• The output shows that the calculated value is 33.