How to Evaluate Postfix Expression using Stack Data Structure - Algorithm & Code

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

#define MAX_SIZE 100

// Stack structure
struct Stack {
    int top;
    int items[MAX_SIZE];
};

// Function to initialize the stack
void initStack(struct Stack* stack) {
    stack->top = -1;
}

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

// Function to check if stack is full
int isFull(struct Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

// Function to push an element onto stack
void push(struct Stack* stack, int value) {
    if (isFull(stack)) {
        printf("Stack Overflow!\n");
        return;
    }
    stack->items[++stack->top] = value;
}

// Function to pop an element from stack
int pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow!\n");
        return -1;
    }
    return stack->items[stack->top--];
}

// Function to evaluate a Postfix expression
int evaluatePostfix(char* expression) {
    struct Stack stack;
    initStack(&stack);
    
    int i = 0;
    
    while (expression[i] != '\0') {
        // Skip whitespace
        if (expression[i] == ' ') {
            i++;
            continue;
        }
        
        // If the character is a digit, extract the full number
        if (isdigit(expression[i])) {
            int num = 0;
            while (isdigit(expression[i])) {
                num = num * 10 + (expression[i] - '0');
                i++;
            }
            push(&stack, num);
        }
        // If the character is an operator
        else if (expression[i] == '+' || expression[i] == '-' || 
                 expression[i] == '*' || expression[i] == '/') {
            
            // Pop two operands
            int operand2 = pop(&stack);  // Second operand (top of stack)
            int operand1 = pop(&stack);  // First operand
            
            int result;
            
            switch (expression[i]) {
                case '+':
                    result = operand1 + operand2;
                    break;
                case '-':
                    result = operand1 - operand2;
                    break;
                case '*':
                    result = operand1 * operand2;
                    break;
                case '/':
                    if (operand2 == 0) {
                        printf("Error: Division by zero!\n");
                        return 0;
                    }
                    result = operand1 / operand2;
                    break;
            }
            
            // Push the result back onto the stack
            push(&stack, result);
            i++;
        }
        else {
            i++;  // Skip unknown characters
        }
    }
    
    // The final result is at the top of the stack
    return pop(&stack);
}

int main() {
    char expression1[] = "5 3 +";
    char expression2[] = "5 1 2 + 4 * + 3 -";
    char expression3[] = "10 3 -";
    char expression4[] = "2 3 1 * + 9 -";
    
    printf("Postfix: %s\n", expression1);
    printf("Result: %d\n\n", evaluatePostfix(expression1));
    
    printf("Postfix: %s\n", expression2);
    printf("Result: %d\n\n", evaluatePostfix(expression2));
    
    printf("Postfix: %s\n", expression3);
    printf("Result: %d\n\n", evaluatePostfix(expression3));
    
    printf("Postfix: %s\n", expression4);
    printf("Result: %d\n\n", evaluatePostfix(expression4));
    
    return 0;
}

Postfix: 5 3 +
Result: 8

Postfix: 5 1 2 + 4 * + 3 -
Result: 14

Postfix: 10 3 -
Result: 7

Postfix: 2 3 1 * + 9 -
Result: -4

class Stack {
    constructor() {
        this.items = [];
    }
    
    push(element) {
        this.items.push(element);
    }
    
    pop() {
        if (this.isEmpty()) {
            return null;
        }
        return this.items.pop();
    }
    
    isEmpty() {
        return this.items.length === 0;
    }
    
    peek() {
        return this.items[this.items.length - 1];
    }
}

function evaluatePostfix(expression) {
    const stack = new Stack();
    const tokens = expression.split(' ');
    
    for (let token of tokens) {
        // Skip empty tokens
        if (token === '') continue;
        
        // If token is a number, push it to stack
        if (!isNaN(token)) {
            stack.push(parseFloat(token));
        }
        // If token is an operator
        else if (['+', '-', '*', '/'].includes(token)) {
            // Pop two operands
            const operand2 = stack.pop();  // Second operand (top)
            const operand1 = stack.pop();  // First operand
            
            let result;
            
            switch (token) {
                case '+':
                    result = operand1 + operand2;
                    break;
                case '-':
                    result = operand1 - operand2;
                    break;
                case '*':
                    result = operand1 * operand2;
                    break;
                case '/':
                    if (operand2 === 0) {
                        throw new Error("Division by zero!");
                    }
                    result = operand1 / operand2;
                    break;
            }
            
            // Push result back to stack
            stack.push(result);
        }
    }
    
    // Return the final result
    return stack.pop();
}

// Test the function
console.log("Postfix: 5 3 +");
console.log("Result:", evaluatePostfix("5 3 +"));

console.log("\nPostfix: 5 1 2 + 4 * + 3 -");
console.log("Result:", evaluatePostfix("5 1 2 + 4 * + 3 -"));

console.log("\nPostfix: 10 3 -");
console.log("Result:", evaluatePostfix("10 3 -"));

console.log("\nPostfix: 2 3 1 * + 9 -");
console.log("Result:", evaluatePostfix("2 3 1 * + 9 -"));

Postfix: 5 3 +
Result: 8

Postfix: 5 1 2 + 4 * + 3 -
Result: 14

Postfix: 10 3 -
Result: 7

Postfix: 2 3 1 * + 9 -
Result: -4