Evaluation of Postfix Expression

How to Evaluate a Postfix Expression

1. Traverse the expression: We iterate through each character of the postfix expression from left to right.
2. Push operands onto a stack: When encountering a number (operand), push it onto a stack.
3. Apply operators: When an operator is encountered, pop the required number of operands from the stack, perform the operation, and push the result back onto the stack.
4. End condition: After traversing the entire expression, the result will be the single value left on the stack.

Algorithm

1. Initialize an empty stack.
2. Read the postfix expression character by character:
   • If the character is an operand, push it to the stack.
   • If the character is an operator, pop two operands from the stack, apply the operator, and push the result back onto the stack.
3. At the end, the value left in the stack is the result of the postfix expression.

Example

Let’s take the postfix expression:

53+82-*

This corresponds to the infix expression:

(5 + 3) * (8 - 2) = 48

C Program to Evaluate Postfix Expression

#include <stdio.h>
#include <ctype.h>  // For isdigit() function
#include <stdlib.h> // For exit() function

#define MAX 100

// Stack structure
int stack[MAX];
int top = -1;

// Push function
void push(int value) 
{
    if (top == MAX - 1) 
{
        printf("Stack Overflow\n");
        exit(1);
    }
    stack[++top] = value;
}

// Pop function
int pop() 
{
    if (top == -1) 
{
        printf("Stack Underflow\n");
        exit(1);
    }
    return stack[top--];
}

// Function to evaluate postfix expression
int evaluatePostfix(char* expression) 
{
    int i = 0;
    while (expression[i] != '\0') 
{
        // If the character is an operand (digit), push it to the stack
        if (isdigit(expression[i])) 
{
            push(expression[i] - '0');  // Convert char to int
        } 
        // If the character is an operator, pop two elements and apply the operator
        else 
{
            int val1 = pop();
            int val2 = pop();
            
            switch (expression[i]) 
{
                case '+': push(val2 + val1); break;
                case '-': push(val2 - val1); break;
                case '*': push(val2 * val1); break;
                case '/': push(val2 / val1); break;
                default: 
                    printf("Invalid operator encountered\n");
                    exit(1);
            }
        }
        i++;
    }
    
    // The result will be the last element in the stack
    return pop();
}

int main() 
{
    char postfixExpression[] = "53+82-*";
    printf("Postfix Expression: %s\n", postfixExpression);
    int result = evaluatePostfix(postfixExpression);
    printf("Result of the Postfix Expression: %d\n", result);
    return 0;
}

Explanation of the Code

1. Stack: We use an array stack[] to implement the stack, with top keeping track of the top of the stack.
2. Push and Pop Functions: These handle adding and removing elements from the stack.
   • push(int value) adds an element to the top of the stack.
   • pop() removes the top element from the stack and returns it.
3. Main Function:
   • The postfix expression 53+82-* is passed to the evaluatePostfix() function.
   • The function processes each character of the expression. If it is a digit, it is pushed onto the stack. If it is an operator, two operands are popped from the stack, the operation is performed, and the result is pushed back onto the stack.
4. Switch-Case: Used to apply the correct operator on the two popped values.
5. Final Result: After evaluating the entire expression, the result is stored at the top of the stack, and we print it.

Example Walkthrough

For the expression 53+82-*:

1. Push 5 onto the stack.
2. Push 3 onto the stack.
3. Encounter +: Pop 5 and 3, calculate 5 + 3 = 8, push 8.
4. Push 8 onto the stack.
5. Push 2 onto the stack.
6. Encounter -: Pop 8 and 2, calculate 8 - 2 = 6, push 6.
7. Encounter *: Pop 8 and 6, calculate 8 * 6 = 48, push 48.

Final result: 48.

Output

Postfix Expression: 53+82-*
Result of the Postfix Expression: 48

This simple program demonstrates how to evaluate postfix expressions using a stack. By using stack operations (push and pop), we can easily handle any postfix expression.