to postfix, step by step using the stack method
Precedence Recap
Operator Precedence Associativity
• / 2 Left
+ - 1 Left
Step-by-Step Table
Step Symbol Action Stack Postfix
1 A Operand → Add to output a
2 + Stack empty → Push + + a
3 B Operand → Add to output + ab
4 * * has higher precedence than + → Push * +* ab
5 C Operand → Add to output +* abc
6 + Incoming + has lower precedence than * → Pop * first → + abc*
Output becomes a b c *
Now stack top is +, incoming is + (equal precedence, left
assoc.) → Pop old + abc*+
Push new +
abc*+
7 D Operand → Add to output + abc*+d
8 End Pop remaining + abc*+d+
Final Postfix Expression
abc∗+d+
Why this happens
● Multiplication * is evaluated before addition +, so b*c forms first.
● Then a is added → (a + (b*c))
● Finally d is added → ((a + (b*c)) + d).
The postfix eliminates the need for parentheses because the order is built into the operator
positions.
Expression:
x-y/z-k*d
Operator Precedence
Operator Precedence Associativity
/* 2 Left
-+ 1 Left
Infix → Postfix Table
Step Symbol Action Stack Postfix
Expression
1 x Operand → add to output x
2 - Operator → push onto stack - x
3 y Operand → add to output - xy
4 / Higher precedence than - → push onto -/ xy
stack
5 z Operand → add to output -/ xyz
6 - Lower precedence than / → pop / then - , - xyz/-
then push new -
7 k Operand → add to output - xyz/-k
8 * Higher precedence than - → push onto -* xyz/-k
stack
9 d Operand → add to output -* xyz/-kd
10 End Pop remaining operators (* then -) xyz/-kd*-
Final Postfix Expression:
xyz/−kd∗−
Why This Is Useful
Infix Postfix
x-y/z-k*d xyz/-kd*-
Requires precedence rules Evaluated directly with a stack
Postfix avoids ambiguity, no parentheses needed, and is easy for machines to evaluate
sequentially
Here’s the postfix conversion for the infix expression:
Infix: A - B / C * A / K - L
--A/*/BCAKL
Operator rules
Op Prec Assoc
/* 2 Left
+- 1 Left
Step-by-step (stack method)
Ste Symbo Action Stack Output
p l
1 A Operand → output A
2 - Push - A
3 B Operand → output - AB
4 / Higher prec than - → push -/ AB
5 C Operand → output -/ ABC
6 * Equal prec to / (left-assoc) → pop /, then push * -* ABC/
7 A Operand → output -* ABC/A
8 / Equal prec to * (left-assoc) → pop *, then push / -/ ABC/A*
9 K Operand → output -/ ABC/A*K
10 - Lower than / → pop /; equal to - (left-assoc) → - ABC/A*K/-
pop -; push new -
11 L Operand → output - ABC/A*K/-L
12 End Pop remaining operators ABC/A*K/-L-
Infix: (A - B) * C
Goal: Postfix
Stack method (steps)
Step Symbol Action Stack Output
1 ( Push (
2 A Operand → output ( A
3 - Push (- A
4 B Operand → output (- AB
5 ) Pop until ( → output -, AB-
discard (
6 * Push * AB-
7 C Operand → output * AB–C
8 End Pop remaining operators AB-C*
Postfix result
AB-C*
1) Postfix already encodes order
• In infix, parentheses force the order (e.g., do (P - Q) before * R).
• In postfix, the position of operators already fixes the order, so no brackets are needed.
o Example: (P - Q) * R → P Q - R *
Here - comes right after P Q, so subtraction must happen before the *. Brackets
would be redundant.
2) Brackets are control signals during conversion, not tokens to keep
• When you see (, you push it on the stack to mark a protected zone.
• When you see ), you pop operators to output until you meet (, then discard both
parentheses.
• They control the shunting process but aren’t part of the final expression.
3) Only operands & operators belong to postfix
• Postfix is a sequence of operands followed by operators in the exact execution order.
• Parentheses are only needed in infix to resolve ambiguity; postfix has no ambiguity to
resolve.
Infix: (P - Q) * R / (S + T)
Goal: Postfix
Stack method (step-by-step)
Step Symbol Action Stack Output
1 ( Push (
2 P Operand → output ( P
3 - Push (- P
4 Q Operand → output (- PQ
5 ) Pop until ( → output -, discard ( PQ-
6 * Push * PQ-
7 R Operand → output * PQ–R
8 / /' and '*' have equal prec (left-assoc) → pop *, then / PQ-R*
push /`
9 ( Push /( PQ-R*
10 S Operand → output /( PQ-R*S
11 + Push /(+ PQ-R*S
12 T Operand → output /(+ PQ-R*ST
13 ) Pop until ( → output +, discard ( / PQ-R*ST+
14 End Pop remaining operators PQ-R*ST+/
Postfix result
PQ−R∗ST+/
Prefix conversion
A + B * C to prefix
1. Reverse tokens (no parentheses here):
A+B*C→C*B+A
2. Postfix of the reversed expression (C * B + A):
Step Sym Action Stack Output
1 C Operand → output C
2 * Push * C
3 B Operand → output * CB
4 + Lower prec than * → pop *, then push + + CB*
5 A Operand → output + CB*A
6 End Pop remaining CB*A+
Postfix (of reversed) = C B * A +
3. Reverse that postfix to get prefix of the original:
+A*BC
Quiz Question Postfix and prefix
a) Convert the following Infix expression to postfix and prefix
A+B/C+D*E-F/G+H*I-J
We’ll convert this infix expression:
A+B/C+D*E-F/G+H*I–J
1) Infix → Postfix (step-by-step stack dry run)
Rules used
• Precedence: * / > + -
• All operators are left-associative.
• Output queue holds the result; operator stack holds operators.
Token Action Output Operator Stack
A add operand to output A —
+ push (stack empty) A +
B add operand AB +
/ higher than + → push AB +/
C add operand ABC +/
(end of pop / to output ABC/ +
/)
+ same precedence as +, ABC/+ +
left-assoc → pop +,
then push new +
D add operand ABC/+D +
* higher than + → push ABC/+D +*
E add operand ABC/+DE +*
(end of pop * to output ABC/+DE* +
*)
- - has same precedence ABC/+DE*+ -
as +, left-assoc → pop
+, then push -
F add operand ABC/+DE*+F -
/ higher than - → push ABC/+DE*+F -/
G add operand ABC/+DE*+FG -/
(end of pop / to output ABC/+DE*+FG/ -
/)
+ + has same ABC/+DE*+FG/- +
precedence as -, left-
assoc → pop -, then
push +
H add operand ABC/+DE*+FG/-H +
* higher than + → push ABC/+DE*+FG/-H +*
I add operand ABC/+DE*+FG/-HI +*
(end of pop * to output ABC/+DE*+FG/-HI* +
*)
- - has same precedence ABC/+DE*+FG/-HI*+ -
as +, left-assoc → pop
+, then push -
J add operand ABC/+DE*+FG/-HI*+J -
(end) pop remaining ops ABC/+DE*+FG/-HI*+J- —
Postfix result
ABC/+DE*+FG/-HI*+J-
2) Infix → Prefix (clean method)
Trick: Reverse the infix, swap associativity handling as needed, convert to postfix, then reverse
the result.
Step A: Reverse tokens (no parentheses here)
Original:
A+B/C+D*E-F/G+H*I-J
Reversed tokens:
J-I*H+G/F-E*D+C/B+A
Step B: Run the same postfix algorithm on this reversed sequence
(When using this reverse method, the usual implementation note is to treat operators as if
scanned right-to-left; with no parentheses here, the basic precedence/left-assoc rules still drive
the stack pops correctly.)
Dry run (reversed input)
Token Action Output Op Stack
J operand → out J —
- Push J -
I Out JI -
* * > - → push JI -*
H Out JIH -*
(end *) pop * JIH* -
+ + has ≥ -? (same J I H * - +
precedence; left-
assoc) → pop -,
push +
G Out JIH*-G +
/ *// > + → push JIH*-G +/
F Out JIH*-GF +/
(end /) pop / JIH*-GF/ +
- - has ≥ + (same), JIH*-GF/+ -
left-assoc → pop
+, push -
E Out JIH*-GF/+E -
* * > - → push JIH*-GF/+E -*
D Out JIH*-GF/+E -*
D
(end *) pop * JIH*-GF/+E -
D*
+ + ≥ - (same), JIH*-GF/+E +
left-assoc → pop D*-
-, push +
C Out JIH*-GF/+E +
D*-C
/ / > + → push JIH*-GF/+E +/
D*-C
B Out JIH*-GF/+E +/
D*-CB
(end /) pop / JIH*-GF/+E +
D*-CB/
+ + ≥ + (same), JIH*-GF/+E +
left-assoc → pop D*-CB/+
+, push new +
A Out JIH*-GF/+E +
D*-CB/+A
(end) pop remaining JIH*-GF/+E —
D*-CB/+A+
So the postfix of the reversed input is:
JIH*-GF/+ED*-CB/+A+
Step C: Reverse this to get prefix
Reverse token order:
+A+/BC-*DE+/FG-*HIJ