📌 Evaluation of Postfix Expression Using Stack

Postfix notation (Reverse Polish Notation - RPN) is an operator notation where operators are placed after their operands. This eliminates the need for parentheses and follows a straightforward evaluation using a stack.

---

1️⃣ Why Use Postfix Notation?

✅ No Parentheses Needed → Operator precedence is naturally handled.
✅ Easier Computation → Uses a stack for evaluation.
✅ Used in Compilers & Calculators → Faster execution.

---

2️⃣ Algorithm for Evaluating a Postfix Expression

1️⃣ Scan the postfix expression from left to right.
2️⃣ If an operand (0-9, A-Z) appears, push it onto the stack.
3️⃣ *If an operator (+, -, , /, ^) appears:

• Pop the top two elements from the stack.
• Apply the operator on these elements.
• Push the result back onto the stack.
  4️⃣ Final value in the stack is the result.

---

3️⃣ Example Walkthrough

Evaluate:

6 2 + 5 * 8 4 / -

🔹 Step-by-step Stack Processing

Step	Symbol	Stack After Processing
1	6	6
2	2	6 2
3	+	8
4	5	8 5
5	*	40
6	8	40 8
7	4	40 8 4
8	/	40 2
9	-	38

✅ Final Answer: 38

---

4️⃣ C Program: Evaluate Postfix Expression Using Stack

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

#define MAX 100

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

// Push function
void push(int value) {
    stack[++top] = value;
}

// Pop function
int pop() {
    if (top == -1) return -1;
    return stack[top--];
}

// Evaluate postfix expression
int evaluatePostfix(char* postfix) {
    for (int i = 0; postfix[i] != '\0'; i++) {
        if (isdigit(postfix[i])) {
            push(postfix[i] - '0');  // Convert char to int
        } else {
            int val2 = pop();
            int val1 = pop();
            switch (postfix[i]) {
                case '+': push(val1 + val2); break;
                case '-': push(val1 - val2); break;
                case '*': push(val1 * val2); break;
                case '/': push(val1 / val2); break;
            }
        }
    }
    return pop();
}

int main() {
    char postfix[MAX];
    printf("Enter postfix expression: ");
    scanf("%s", postfix);
    
    printf("Result: %d\n", evaluatePostfix(postfix));
    return 0;
}

---

5️⃣ Complexity Analysis

🔹 Time Complexity: O(n) (Each character is processed once).
🔹 Space Complexity: O(n) (For stack storage).

---

6️⃣ Summary Table of Postfix Evaluation Steps

Operation	Time Complexity
Scanning Expression	O(n)
Push Operand	O(1)
Pop Operand	O(1)
Compute & Push Result	O(1)
Final Result	O(1)