Q.Let us now use this algorithm (Algorithm 3.1) to convert a given infix expression (x + y)/(z*8) into equivalent postfix expression using a stack. Figure 3.3 shows the steps to be followed on encountering an operator or an operand in the given infix expression. Note here that stack is used to track the operators and parentheses, and a string variable contains the equivalent postfix expression.
You're viewing a preview — the full solution, concept, methods & PYQ mapping are locked.
Start your 14-day free trial to unlock the full solution →
A stack converts infix to postfix in ONE left-to-right scan: operands go straight to the output, operators wait on the stack until an operator of lower precedence (or a closing bracket, or the end of input) forces them out. (x + y)/(z*8) becomes xy+z8*/.
Concept understanding — why a stack at all?
In infix notation the position of an operator does not tell you when to apply it; precedence and brackets do. Postfix removes that ambiguity — an operator always appears immediately after both of its operands, so no brackets and no precedence rules are needed at evaluation time.
The conversion needs a place to park an operator while we wait to see whether something of higher precedence comes next. That parking place is last-in-first-out: the operator we parked most recently is the one that must come out first. That is exactly a stack.
The algorithm (Algorithm 3.1)
- If the symbol is an operand, append it to the postfix string.
- If the symbol is
(, push it onto the stack. - If the symbol is
), pop and append operators until a(is popped. Discard both brackets — they never appear in postfix. - If the symbol is an operator, pop and append every operator on top of the stack that has higher or equal precedence (stop at a
(), then push the current operator. - After the scan, pop and append all remaining operators.
Precedence used here: * and / (higher) > + and - (lower). A ( on the stack acts as a wall — nothing is popped past it except by a matching ).
Step-by-step trace of (x + y)/(z*8)
| Step | Symbol | Action | Stack (bottom → top) | Postfix string |
|---|---|---|---|---|
| 1 | ( | push bracket | ( | (empty) |
| 2 | x | operand → output | ( | x |
| 3 | + | top is ( → nothing to pop; push + | ( + | x |
| 4 | y | operand → output | ( + | xy |
| 5 | ) | pop until ( → + out; discard ( | (empty) | xy+ |
| 6 | / | stack empty → push / | / | xy+ |
| 7 | ( | push bracket | / ( | xy+ |
| 8 | z | operand → output | / ( | xy+z |
| 9 | * | top is ( → nothing to pop; push * | / ( * | xy+z |
| 10 | 8 | operand → output | / ( * | xy+z8 |
| 11 | ) | pop until ( → * out; discard ( | / | xy+z8* |
| 12 | end | pop the rest → / out | (empty) | xy+z8*/ |
At step 5 the + is released only because the closing bracket forces it. At step 11 the * is released the same way. The / waits until the very end because nothing ever outranks it — this is why it lands last in the postfix string.
Program
def precedence(op):
if op in ('*', '/'):
return 2
if op in ('+', '-'):
return 1
return 0
def infix_to_postfix(expr):
stack = []
postfix = ''
for ch in expr:
if ch == ' ':
continue
elif ch.isalnum(): # operand …
Unlock everything free for 14 days
- Full step-by-step solutions
- Concept-first explanations
- Methods, shortcuts & mistakes
- PYQ mapping + timed mock tests
Full access for 14 days. No credit card required.