📌 Application of Stack: Prefix and Postfix Expressions

Stacks are extensively used in expression evaluation and conversion, particularly for handling prefix and postfix expressions. These notations eliminate the need for parentheses and operator precedence rules, making computations more efficient.

🚀 Topics Covered:

✅ Infix, Prefix, and Postfix Notations
✅ Why Stacks are Used in Expression Evaluation
✅ Conversion from Infix to Postfix & Prefix
✅ Evaluating Postfix Expressions using Stack

---

1️⃣ Expression Notations

(a) Infix Notation (Standard Form)

• Operators are between operands.
• Requires operator precedence and parentheses for clarity.
• Example:

  
  (3 + 5) * 2
  

(b) Prefix Notation (Polish Notation)

• Operators before operands.
• Example:

  
  * + 3 5 2  → Equivalent to (3 + 5) * 2
  

(c) Postfix Notation (Reverse Polish Notation - RPN)

• Operators after operands.
• Example:

  
  3 5 + 2 *  → Equivalent to (3 + 5) * 2
  

💡 Why Use Prefix/Postfix?

• No need for parentheses.
• Easier and faster computation using stacks.
• Widely used in compilers and calculators.

---

2️⃣ Why Stacks are Used in Expression Evaluation?

Stacks help in: ✔ Converting infix expressions to postfix or prefix.
✔ Evaluating postfix expressions efficiently.

---

3️⃣ Conversion: Infix to Postfix Using Stack

Algorithm to Convert Infix to Postfix

1️⃣ Scan the infix expression from left to right.
2️⃣ Operands (A-Z, 0-9) → Directly append to the result.
3️⃣ *Operators (+, -, , /, ^) → Push to stack, considering precedence.
4️⃣ Parentheses Handling

• '(' → Push to stack.
• ')' → Pop from stack until '(' is found.
  5️⃣ Pop remaining operators after scanning.

Example:

Convert:

A + B * C  

🔹 Stack Process

Step	Symbol	Stack	Postfix Expression
1	A		A
2	+	+	A
3	B	+	A B
4	*	+ *	A B
5	C	+ *	A B C
6	(End)		A B C * +

✅ Postfix Expression:

A B C * +

C Implementation: Infix to Postfix Conversion

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

#define MAX 100

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

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

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

// Operator precedence function
int precedence(char c) {
    if (c == '^') return 3;
    if (c == '*' || c == '/') return 2;
    if (c == '+' || c == '-') return 1;
    return 0;
}

// Convert infix to postfix
void infixToPostfix(char* infix) {
    char postfix[MAX];
    int j = 0;
    
    for (int i = 0; infix[i] != '\0'; i++) {
        if (isalnum(infix[i])) {  
            postfix[j++] = infix[i];  // Append operand to postfix
        } 
        else if (infix[i] == '(') {
            push(infix[i]);
        } 
        else if (infix[i] == ')') {
            while (top != -1 && stack[top] != '(') {
                postfix[j++] = pop();
            }
            pop();  // Remove '('
        } 
        else {
            while (top != -1 && precedence(stack[top]) >= precedence(infix[i])) {
                postfix[j++] = pop();
            }
            push(infix[i]);
        }
    }

    while (top != -1) {
        postfix[j++] = pop();
    }
    postfix[j] = '\0';
    
    printf("Postfix: %s\n", postfix);
}

int main() {
    char infix[MAX];
    printf("Enter infix expression: ");
    scanf("%s", infix);
    
    infixToPostfix(infix);
    return 0;
}

🔹 Time Complexity: O(n)

---

4️⃣ Evaluating Postfix Expression Using Stack

Algorithm for Postfix Evaluation

1️⃣ Scan the postfix expression from left to right.
2️⃣ Operands (A-Z, 0-9) → Push onto stack.
3️⃣ *Operators (+, -, , /, ^) → Pop two operands, apply the operation, push result.
4️⃣ Final value in the stack is the result.

Example:

Evaluate:

6 2 + 5 * 8 4 / -

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

---

C Implementation: Postfix Evaluation

#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;
}

🔹 Time Complexity: O(n)

---

5️⃣ Summary Table: Stack Operations in Expression Handling

Operation	Time Complexity
Infix to Postfix	O(n)
Postfix Evaluation	O(n)
Prefix Evaluation	O(n)

---