Q.Write an algorithm to evaluate any prefix expression using a stack.
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 →Scan the prefix expression right to left, push operands onto a stack, and on each operator pop two operands, apply the operator with the first-popped value as the LEFT operand, and push the result back. One value remains at the end — that is the answer.
Why a stack, and why right-to-left?
In a prefix (Polish) expression the operator comes before its two operands: + 3 4 means 3 + 4. So when you meet an operator, its operands are somewhere to its right — and they may themselves be whole sub-expressions, e.g. - * 5 4 + 3 2 means (5 × 4) − (3 + 2).
That is exactly the structure a stack is built for. If you scan from the right-hand end, then by the time you reach any operator, both of its operands have already been scanned and their values are sitting on top of the stack, innermost first. The operator simply consumes the top two values and pushes back a single value in their place — which then behaves as one operand for whatever operator lies further left.
Evaluating left to right would not work: you would meet an operator before you had seen either of its operands.
The algorithm
ALGORITHM EvaluatePrefix(expr)
1. Create an empty stack S.
2. Scan expr from RIGHT to LEFT, one token at a time:
3. if token is an OPERAND:
4. S.push(token)
5. else if token is an OPERATOR:
6. op1 = S.pop() # first popped -> LEFT operand
7. op2 = S.pop() # second popped -> RIGHT operand
8. result = op1 <operator> op2
9. S.push(result)
10. end scan
11. value = S.pop() # the only element left
12. return value
The operand-order rule (this is where marks are lost)
In prefix, the first value popped is the LEFT operand: result = op1 - op2.
In postfix, it is the other way round: result = op2 - op1.
For + and × it makes no difference, so a wrong rule goes unnoticed — until the paper sets − or /, and then every answer is wrong.
Worked trace
Evaluate - * 5 4 + 3 2, i.e. (5 × 4) − (3 + 2). Scan right to left:
| Token | Action | Stack (top on the right) |
|---|---|---|
2 | operand → push | 2 |
3 | operand → push | 2, 3 |
+ | pop 3, pop 2 → 3 + 2 = 5 → push | 2 … → 5 |
4 | operand → push | 5, 4 |
5 | operand → push | 5, 4, 5 |
* | pop 5, pop 4 → 5 × 4 = 20 → push | 5, 20 |
- | pop 20, pop 5 → 20 − 5 = 15 → push | 15 |
Scan complete; pop the single remaining value → 15. And indeed (5 × 4) − (3 + 2) = 20 − 5 = 15. ✓
Notice the - step: the first value popped was 20, and it correctly became the left operand of the subtraction. Had we written 5 − 20 we would have got −15.
Implementation in Python
def evaluate_prefix(expr):
stack = []
tokens = expr.split()
# scan RIGHT to LEFT
for token in reversed(tokens): …
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.