✅ Step-by-Step: Infix to Postfix Conversion
Rules:
- Operands (A-Z or numbers): Go directly to the output.
- Left Parenthesis
(: Push to stack. - Right Parenthesis
): Pop from stack to output until(is found.- When you see a right parenthesis
)in the infix expression, you do the following:- Start popping operators from the stack.
- Add each popped operator to the output.
- Stop popping when you find a left parenthesis
(. - Do NOT add the
(or)to the output. Just discard both.
- When you see a right parenthesis
- Operators (+, -,* , /, ^):
- Pop from the stack to output while the top of the stack has equal or higher precedence.
- Then push the current operator.
- When you see an operator (like
+,-,*,/, or^) in the infix expression: - Look at the top of the stack.
- If the top of the stack has an operator with higher or equal precedence, pop it from the stack and add it to the output.
- Repeat step 2 until:
- The stack is empty,
- Or the top of the stack is a left parenthesis
(, - Or the top of the stack has lower precedence than the current operator.
- Push the current operator to the stack.
- When you see an operator (like
🔑 Parentheses Are Not Operators
Even though parentheses control precedence, they are not operators, and so they are not part of the precedence comparison logic used for popping operators from the stack.
They are used only as markers to say:
“Don’t pop past this point!”
Operator Precedence (High to Low):
^(Right associative)*and/(Left associative)+and-(Left associative)
🔺 Operator Precedence Table (High ➡ Low)
| Precedence Level | Operators | Associativity | Notes |
|---|---|---|---|
| 1 (Highest) | ^ | Right-to-left | Exponentiation |
| 2 | *, / | Left-to-right | Multiplication and Division |
| 3 (Lowest) | +, - | Left-to-right | Addition and Subtraction |
✅ What is Associativity?
Associativity tells us the direction in which operators of the same precedence level are evaluated when they appear next to each other.
🔁 Two Types of Associativity:
| Type | Meaning |
|---|---|
| Left-to-right | Evaluate from left to right |
| Right-to-left | Evaluate from right to left |
🧠 Why It Matters
Associativity only matters when you have two or more operators of the same precedence level next to each other.
🔍 Examples:
1. Left-to-right associativity (for +, -, *, /):
- Subtraction (
-) is left-to-right, so:100 - 50 = 50, then50 - 10 = 40
2. Right-to-left associativity (for ^):
- Exponentiation is right-to-left, so:
- First
3 ^ 2 = 9 - Then
2 ^ 9 = 512
- First
If you did it left-to-right (2 ^ 3 = 8, then 8 ^ 2 = 64) — that would be wrong.
💡 Example: Infix → Postfix
Infix: (A + B) * C
Steps:
(→ pushA→ output →A+→ pushB→ output →A B)→ pop till(→A B +*→ pushC→ output →A B + C- End → pop
*→A B + C *
Postfix: A B + C *
📝 Practice Problems
🔁 Convert Infix to Postfix:
(A + B) * (C - D)A + B * CA * (B + C) / D(A + B) * (C + D)A + B + C + D
✅ Evaluate Postfix Expression (Assume A=2, B=3, C=4, D=5):
A B + C *A B C * +A B + C D - *A B + C + D +
🧠 Challenge: Identify Expression Type
Label the following as Infix, Postfix, or Prefix:
A B + C *+ A B(A + B) * C* + A B CA B C * +
Answers:
📝 Convert Infix to Postfix
| Infix Expression | Postfix Expression |
|---|---|
(A + B) * (C - D) | A B + C D - * |
A + B * C | A B C * + |
A * (B + C) / D | A B C + * D / |
(A + B) * (C + D) | A B + C D + * |
A + B + C + D | A B + C + D + |
✅ Evaluate Postfix Expression
Given: A = 2, B = 3, C = 4, D = 5
| Postfix Expression | Step-by-Step Evaluation | Result |
|---|---|---|
A B + C * | (2 + 3) * 4 = 5 * 4 | 20 |
A B C * + | 3 * 4 = 12, then 2 + 12 | 14 |
A B + C D - * | (2 + 3) = 5, (4 - 5) = -1, 5 * -1 | -5 |
A B + C + D + | 2 + 3 = 5, 5 + 4 = 9, 9 + 5 = 14 | 14 |
🧠 Identify Expression Type
| Expression | Type | Reason |
|---|---|---|
A B + C * | Postfix | Operators come after operands |
+ A B | Prefix | Operators come before operands |
(A + B) * C | Infix | Operators are between operands |
* + A B C | Prefix | First operator is at start, all in prefix order |
A B C * + | Postfix | Operands first, operators at the end |