DS Menu

Postfix Evaluation



Evaluating a postfix expression (also known as Reverse Polish Notation), it using a stack is a straight forward process that involves scanning the expression from left to right and using a stack to store operands. When an operator is encountered, operands are popped from the stack, the operation is performed, and the result is pushed back onto the stack. This method is efficient and doesn't require parentheses or operator precedence rules.

Steps for Evaluating Postfix Expression:

  1. Initialize an Empty Stack: This stack will hold operands and intermediate results.
  2. Scan the Postfix Expression from Left to Right:
    • If the Symbol is an Operand: Push it onto the stack.
    • If the Symbol is an Operator: Pop the top two operands from the stack, perform the operation, and push the result back onto the stack.
  3. Repeat Until the End of the Expression.
  4. The Result: At the end of the expression, the stack will contain one element, which is the final result

Example to evaluate postfix expression "5 3 + 8 2 - *".

postfix expression Stack Explanation
5 3 + 8 2 - *
3 + 8 2 - * 5 5: Operand → Push onto stack
+ 8 2 - * 3
5		 3: Operand → Push onto stack
8 2 - * 8 +: Operator → Pop 3 and 5, calculate 5 + 3 = 8, push result onto stack
2 - * 8
8		 8: Operand → Push onto stack
- * 2
8
8		 2: Operand → Push onto stack
* 6
8		 -: Operator → Pop 2 and 8, calculate 8 - 2 = 6, push result onto stack
48 *: Operator → Pop 6 and 8, calculate 8 * 6 = 48

End of Expression: The stack contains 48, which is the result.


C Program to evaluate postfix expression

Program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX 15

int stack[MAX];
int top = -1;

// Function to push an element to the stack
void push(int item) {
    if (top >= MAX - 1) {
        printf("\nStack Overflow.");
    } else {
        stack[++top] = item;
    }
}

// Function to pop an element from the stack
int pop() {
    if (top < 0) {
        printf("Stack Underflow.");
        exit(1);
    } else {
        return stack[top--];
    }
}

// Function to evaluate the postfix expression
int evaluatePostfix(char* postfix) {
    int i, op1, op2, result;
    char ch;

    for (i = 0; postfix[i] != '\0'; i++) {
        ch = postfix[i];
        if (isdigit(ch)) {
            // Push operand to stack
            push(ch - '0'); // Convert char to int
        } else {
            // Operator encountered
            // Pop two operands from stack
            op2 = pop();
            op1 = pop();

            switch (ch) {
                case '+': result = op1 + op2; break;
                case '-': result = op1 - op2; break;
                case '*': result = op1 * op2; break;
                case '/': result = op1 / op2; break;
                default: 
                    printf("Invalid operator encountered.");
                    exit(1);
            }

            // Push result back to stack
            push(result);
        }
    }

    // Final result is in the stack
    return pop();
}

// Main function
int main() {
    char postfix[MAX];
    int result;

    printf("Enter Postfix Expression: ");
    gets(postfix);

    result = evaluatePostfix(postfix);
    printf("The result of the Postfix expression is: %d\n", result);

    return 0;
}
Next Topic :Introduction to Dictionaries