This program evaluates a postfix expression using a stack. A postfix expression (also known as Reverse Polish Notation) is a mathematical expression where the operator follows its operands. For example, 3 4 + is the postfix equivalent of the infix expression 3 + 4.

Program Explanation

Postfix expressions are evaluated using a stack because of their straightforward, left-to-right order of execution. The algorithm to evaluate a postfix expression works as follows:

1. Scan the postfix expression from left to right.
2. When you encounter an operand (number), push it onto the stack.
3. When you encounter an operator, pop the required number of operands from the stack, perform the operation, and push the result back onto the stack.
4. After the entire expression has been scanned, the result will be at the top of the stack.

C Program Code

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX 100

// Stack structure
struct Stack {
    int arr[MAX];
    int top;
};

// Initialize the stack
void initStack(struct Stack *s) {
    s->top = -1;
}

// Check if stack is empty
int isEmpty(struct Stack *s) {
    return s->top == -1;
}

// Push an element onto the stack
void push(struct Stack *s, int value) {
    if (s->top == MAX - 1) {
        printf("Stack overflow\n");
        return;
    }
    s->arr[++(s->top)] = value;
}

// Pop an element from the stack
int pop(struct Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return -1;
    }
    return s->arr[(s->top)--];
}

// Evaluate the given operation
int evaluateOperation(int operand1, int operand2, char operator) {
    switch (operator) {
        case '+': return operand1 + operand2;
        case '-': return operand1 - operand2;
        case '*': return operand1 * operand2;
        case '/': 
            if (operand2 == 0) {
                printf("Error: Division by zero\n");
                exit(1);
            }
            return operand1 / operand2;
        default:
            printf("Invalid operator\n");
            exit(1);
    }
}

// Function to evaluate a postfix expression
int evaluatePostfix(char* expression) {
    struct Stack s;
    initStack(&s);

    for (int i = 0; expression[i] != '\0'; i++) {
        char token = expression[i];

        // If token is a whitespace, skip it
        if (token == ' ') continue;

        // If token is an operand, push it onto the stack
        if (isdigit(token)) {
            push(&s, token - '0');
        } 
        // If token is an operator, pop two operands, perform the operation and push the result
        else {
            int operand2 = pop(&s);
            int operand1 = pop(&s);
            int result = evaluateOperation(operand1, operand2, token);
            push(&s, result);
        }
    }

    // The final result will be at the top of the stack
    return pop(&s);
}

// Main driver function
int main() {
    char postfixExpression[] = "6 2 3 + - 3 8 2 / + * 2 3 + /";

    printf("Postfix Expression: %s\n", postfixExpression);
    int result = evaluatePostfix(postfixExpression);
    printf("Result: %d\n", result);

    return 0;
}
    

Code Explanation

1. Stack Structure:
The program defines a stack using an array, and the integer top keeps track of the top element in the stack. Basic stack operations like push(), pop(), and isEmpty() are implemented to handle stack management.

2. Evaluating Postfix Expression:
The core of the program lies in the evaluatePostfix() function, which iterates through the postfix expression:

• For each operand (digit), the value is pushed onto the stack.
• For each operator, two operands are popped from the stack, the operation is performed, and the result is pushed back onto the stack.
• The function evaluateOperation() handles different operations like addition, subtraction, multiplication, and division.

3. Final Result:
After scanning the entire postfix expression, the result will be the only remaining value in the stack, which is then popped and returned.

Sample Output

Postfix Expression: 6 2 3 + - 3 8 2 / + * 2 3 + /
Result: 3
    

Conclusion

This program efficiently evaluates a postfix expression using a stack. It demonstrates how to handle operators and operands in a postfix expression and correctly computes the result by using a stack data structure.