Prefix & Postfix using Stack
• Understanding conversion and evaluation
using stack
Infix, Prefix, Postfix
• - Infix: Operator between operands (A + B)
• - Prefix: Operator before operands (+ A B)
• - Postfix: Operator after operands (A B +)
Why Stack?
• - Handles operator precedence
• - Helps with parentheses
• - Temporary storage of operators
Infix → Postfix (Algorithm)
• 1. Scan expression left to right
• 2. Operand → Add to output
• 3. '(' → Push to stack
• 4. ')' → Pop until '('
• 5. Operator → Pop higher/equal precedence
ops
• 6. Pop all remaining operators at end
• Example: (A + B) * C → A B + C *
Infix → Prefix (Algorithm)
• 1. Reverse infix expression
• (swap '(' and ')')
• 2. Convert to postfix
• 3. Reverse result → prefix
• Example: (A + B) * C → * + A B C
Postfix Evaluation
• 1. Scan expression left to right
• 2. Operand → Push to stack
• 3. Operator → Pop 2 operands, apply, push
result
• 4. Final result at stack top
• Example: 5 6 2 + * → 40
Prefix Evaluation
• 1. Scan expression right to left
• 2. Operand → Push to stack
• 3. Operator → Pop 2 operands, apply, push
result
• 4. Final result at stack top
• Example: * + 5 6 2 → 22
Summary
• - Infix is natural form, but harder for
computers
• - Prefix & Postfix remove ambiguity
• - Stack simplifies conversion & evaluation