DataStructure Infix, Postfix, Prefix Expression
DataStructure Infix, Postfix, Prefix Expression
1. Infix Expression
Definition
An infix expression is a way of writing mathematical expressions where operators are placed between the operands.
This is the form we usually use in everyday mathematics.
• Example:
A+B
Here:
• A and B are operands (values or variables)
• + is the operator
• The operator is between operands → infix
More Examples:
1. A + B - C
2. (A + B) * C
3. (X * Y) + Z
Important Points:
• Infix expressions are easy for humans to read.
• Computers find them harder to evaluate directly because operator precedence and brackets must be considered.
• Example with precedence:
A + B * C means A + (B * C) (multiplication happens before addition).
2. Postfix Expression
Definition
A postfix expression (also called Reverse Polish Notation, RPN) is a way of writing mathematical expressions where the
operator comes after the operands.
• Example:
AB+
Here:
• A and B are operands
• + is the operator
• Operator comes after the operands → postfix
More Examples:
1. A B + C - → equivalent to (A + B) - C
2. A B C * + → equivalent to A + (B * C)
3. X Y * Z + → equivalent to (X * Y) + Z
1 A=2 Push 2
2 B=3 Push 23
4 C=4 Push 54
Final Answer: 20
What is a Prefix Expression?
A prefix expression (also called Polish notation) is a way of writing mathematical expressions where the operator comes
before the operands.
• Form:
Operator Operand1 Operand2
Example
+AB
This means:
A+B
More Examples
Infix (Normal) Prefix (Operator First)
A+B +AB
(A + B) * C * +AB C
(X * Y) + Z +*XYZ
A–B+C + -AB C
Key Points
• No parentheses are needed in prefix notation because the position of the operator tells us the order of evaluation.
• Operator precedence and associativity are handled naturally by the notation.
• Prefix expressions are evaluated from right to left (unlike postfix which is left to right).
• Can be easily converted from infix using a stack.
Example Conversion
Infix:
(A + B) * C
Step 1: Reverse and swap brackets:
C * (B + A)
Step 2: Convert to postfix:
C BA+ *
Step 3: Reverse postfix:
* +AB C
Prefix:
* +AB C
1 4 Push operand 4
2 3 Push operand 43
Answer: 10
Board-style Example: Infix → Prefix
Infix:
A / B + C * (D – E)
Step 1: Reverse & swap brackets:
(E –D )* C+B/A
Step 2: Convert to postfix:
E D - C* BA/ +
Step 3: Reverse postfix:
+/AB* C-ED
Prefix:
+/AB* C-ED
Question1: Transform the following expression to both prefix and postfix form:
(A + B * C – D) / E * F
Notation Expression
Prefix * / - +A* B C D E F
Postfix ABC*+D-E/F*
Q2. Transform the following expressions to infix form:
1. + - ABC
2. + A – BC
Solution: We’ll convert prefix → infix using the standard stack method:
Method (right-to-left):
Scan from right to left.
• If token is an operand, push it.
• If token is an operator, pop two items → left then right, form (left op right), and push back.
1) Prefix: + - A B C
1 C Push operand C
2 B Push operand C, B
3 A Push operand C, B, A
Infix result:
(A − B) + C
2) Prefix: + A − B C
1 C Push operand C
2 B Push operand C, B
Infix result:
A + (B − C)
Q3. Evaluate the following postfix expression using a stack and show the contents of the stack after execution of each
operation 5, 6, 9, +, 80, 5, *, -, /
Solution: Postfix Expression
5 6 9 + 80 5 * - /
1 5 Push operand 5
2 6 Push operand 5, 6
3 9 Push operand 5, 6, 9
1 U Output operand U
2 * Push * * U
3 V Output operand * UV
9 – Push – +/( -
Postfix: U V * R S T - / +
Q2) Convert to postfix
Infix: P / (Q – R) * S + T
1 P Output operand P
2 / Push / / P
3 ( Push ( /( P
4 Q Output operand /( PQ
5 – Push – / (- PQ
Postfix: P Q R - / S * T +
Q3) Convert to postfix
Infix: X / Y + U * (V – W)
1 X Output operand X
2 / Push / / X
3 Y Output operand / XY
9 – Push – + * (- XY/UV
Postfix: X Y / U V W - * +
Q4) Convert to postfix
Infix: P / (Q + (R – T) * U)
1 P Output operand P
2 / Push / / P
3 ( Push ( /( P
4 Q Output operand /( PQ
5 + Push + / (+ PQ
6 ( Push ( / (+ ( PQ
8 – Push – / (+ (- PQR
Postfix: P Q R T - U * + /
Q5) Convert to postfix
Infix: X – Y / (Z + U) * V
1 X Output operand X
2 – Push – – X
3 Y Output operand – XY
5 ( Push ( –/( XY
7 + Push + – / (+ XYZ
Postfix: X Y Z U + / V * -
Q6) Convert to postfix
Infix: A / B + C * (D – E)
1 A Output operand A
2 / Push / / A
3 B Output operand / AB
9 – Push – + * (- AB/CD
Postfix: A B / C D E - * +
Converting Infix to Postfix
Infix: Operators are between operands.
Example: A + B
Postfix: Operators come after operands.
Example: A B +
Example 1: A B + C *
1. A → Push: A
2. B → Push: A B
3. + → Pop B, A → (A + B) → Push: (A + B)
4. C → Push: (A + B) C
5. * → Pop C, (A + B) → ((A + B) * C) → Push.
6. End → Final: ((A + B) * C)
Example 2: A B C * + D -
1. A → Push: A
2. B → Push: A B
3. C → Push: A B C
4. * → Pop C, B → (B * C) → Push: A (B * C)
5. + → Pop (B * C), A → (A + (B * C)) → Push.
6. D → Push: (A + (B * C)) D
7. - → Pop D, (A + (B * C)) → ((A + (B * C)) - D) → Push.
8. End → Final: ((A + (B * C)) - D)
Infix → Postfix Stack for operators Push operands to output, manage operator precedence, use parentheses rules
Postfix → Infix Stack for operands Push operands, when operator appears pop two operands and form (op1 operator op2)
Infix → Postfix
Algorithm Table
Step
Rule / Action
No.
If the symbol is an operator → Pop operators from stack with higher or equal precedence and add to output, then
3
push the current operator.
5 If symbol is ')' → Pop from stack to output until '(' is found; remove '('.
Example Table – (A + B) * C
1 ( Push ( –
2 A Operand → Output ( A
3 + Push (+ A
4 B Operand → Output (+ AB
6 * Push * AB+
Final Postfix: A B + C *
Postfix → Infix
Algorithm Table
Step No. Rule / Action
3 If the symbol is an operator → Pop top two operands → Form (op1 operator op2) → Push result back onto stack.
4 After reading all symbols → The stack will contain the final infix expression.
Example Table – A B + C *
Symbol
Step Action Stack Output (Infix)
Scanned
1 A Operand → Push A –
2 B Operand → Push AB –
3 + Pop B, A → (A + B) → Push (A + B) (A + B)
4 C Operand → Push (A + B) C (A + B)
Pop C, (A + B) → ((A + B) * C)
5 * ((A + B) * C) ((A + B) * C)
→ Push
1 A Push A A –
2 B Push B AB –
3 + Pop B, Pop A → (A + B) (A + B) (A + B)
4 C Push C (A + B) C (A + B)
5 D Push D (A + B) C D (A + B)
6 * Pop D, Pop C → (C * D) (A + B) (C * D) (C * D)
1 A Push A A –
2 C Push C AC –
3 D Push D ACD –
4 + Pop D, Pop C → (C + D) A (C + D) (C + D)
5 E Push E A (C + D) E (C + D)
7 * Pop ((C + D) / E), Pop A → (A * ((C + D) / E)) (A * ((C + D) / E)) (A * ((C + D) / E))
1 3 Push 3 3 –
2 5 Push 5 35 –
4 1 Push 1 81 3+5=8
Final Answer: 8
b) A B * C / D * → 3 5 * 1 / 4 *
Step Symbol Scanned Action Stack Output (Expression Y)
1 3 Push 3 3 –
2 5 Push 5 35 –
4 1 Push 1 15 1 3 × 5 = 15
6 4 Push 4 15 4 15 ÷ 1 = 15
Symbol
Step Action Stack Output (Expression Y)
Scanned
1 A Push A A –
2 B Push B AB –
3 + Pop B, A → (A + B) (A + B) (A + B)
4 C Push C (A + B) C (A + B)
5 D Push D (A + B) C D (A + B)
6 E Push E (A + B) C D E (A + B)
7 / Pop E, D → (D / E) (A + B) C (D / E) (D / E)
((A + B) * (C - D / E)) F
11 G Push G ((A + B) * (C - D / E))
G
((A + B) * (C - D / E)) F
12 H Push H ((A + B) * (C - D / E))
GH
((A + B) * (C - D / E)) F
13 + Pop H, G → (G + H) (G + H)
(G + H)
((A + B) * (C - D / E)) (F
14 * Pop (G + H), F → (F * (G + H)) (F * (G + H))
* (G + H))
Symbol
Step Action Stack Output (Expression Y)
Scanned
1 A Push A A –
2 B Push B AB –
3 + Pop B, A → (A + B) (A + B) (A + B)
4 C Push C (A + B) C (A + B)
9 / Pop F, E → (E / F) ((A + B) - C) D (E / F) (E / F)
(((A + B) - C) * (D + E / F))
12 G Push G (((A + B) - C) * (D + E / F))
G
(((A + B) - C) * (D + E / F))
13 H Push H (((A + B) - C) * (D + E / F))
GH
(((A + B) - C) * (D + E / F))
14 * Pop H, G → (G * H) (G * H)
(G * H)
(((A + B) - C) * (D + E / F))
15 I Push I (((A + B) - C) * (D + E / F))
(G * H) I
(((A + B) - C) * (D + E / F))
16 J Push J (((A + B) - C) * (D + E / F))
(G * H) I J
(((A + B) - C) * (D + E / F))
17 K Push K (((A + B) - C) * (D + E / F))
(G * H) I J K
(((A + B) - C) * (D + E / F))
18 - Pop K, J → (J - K) (J - K)
(G * H) I (J - K)
(((A + B) - C) * (D + E / F))
19 / Pop (J - K), I → (I / (J - K)) (I / (J - K))
(G * H) (I / (J - K))
Final Answer:
(((A+B)−C)×(D+E/F))−((G×H)+(I/(J−K)))
Example 1 (Small)
Postfix Expression:
AB+CD*-
Step-by-Step Table:
1 A Push A A –
2 B Push B AB –
3 + Pop B, A → (A + B) (A + B) (A + B)
4 C Push C (A + B) C (A + B)
5 D Push D (A + B) C D (A + B)
6 * Pop D, C → (C * D) (A + B) (C * D) (C * D)
Final Infix:
(A+B)−(C×D)
Example 2 (Bigger – 12 symbols)
Postfix Expression:
AB+CDE/-*FGH+*+
(This is actually the Postfix form of the earlier Q1(c) big expression.)
Step-by-Step Table:
Symbol
Step Action Stack Output (Expression Y)
Scanned
1 A Push A A –
2 B Push B AB –
3 + Pop B, A → (A + B) (A + B) (A + B)
4 C Push C (A + B) C (A + B)
5 D Push D (A + B) C D (A + B)
6 E Push E (A + B) C D E (A + B)
7 / Pop E, D → (D / E) (A + B) C (D / E) (D / E)
((A + B) * (C - (D / E)))
10 F Push F ((A + B) * (C - (D / E)))
F
Symbol
Step Action Stack Output (Expression Y)
Scanned
((A + B) * (C - (D / E)))
11 G Push G ((A + B) * (C - (D / E)))
FG
((A + B) * (C - (D / E)))
12 H Push H ((A + B) * (C - (D / E)))
FGH
((A + B) * (C - (D / E)))
13 + Pop H, G → (G + H) (G + H)
F (G + H)
((A + B) * (C - (D / E)))
14 * Pop (G + H), F → (F * (G + H)) (F * (G + H))
(F * (G + H))
Final Infix:
((A+B)×(C−(D/E)))+(F×(G+H))