Computer Science · Ch 3 — Stack
Evaluation of Postfix Expression
Evaluation of Postfix Expression
Concept First
When you evaluate an arithmetic expression, the usual way — with operators between operands, like 7 + 8 — is called infix notation. But computers find it much easier to process expressions where operators come after their operands, called postfix notation (also known as Reverse Polish Notation). For example, 7 8 + means "add 7 and 8". The key idea is that a stack is the perfect tool for this job because it lets you store operands as you read them, then combine them when you meet an operator — always using the two most recent values.
The Evaluation Procedure
The textbook gives a clear algorithm (Algorithm 3.2) for evaluating a postfix expression using a stack. For simplicity, we assume all operators are binary operators — that is, they take exactly two operands.
Here is the step-by-step procedure:
- Input the postfix expression into a variable, say
postExp. - For each character in
postExp, repeat step 3. - If the character is an operand (a number), PUSH it onto the stack. Else (the character is an operator), POP two elements from the stack, apply the operator on those two popped elements, and PUSH the computed result back onto the stack.
- After processing all characters: If the stack has exactly one element, POP it and output it as the net result. Else, output "Invalid Postfix expression".
A common mistake is to pop the two operands in the wrong order. When you pop, the first popped value is the right operand and the second popped value is the left operand. For subtraction and division, this order matters.
Worked Example: 7 8 2 * 4 / +
The textbook illustrates this with the postfix expression 7 8 2 * 4 / +. Let's trace it step by step.
| Symbol | Action | Stack (top to bottom) |
|---|---|---|
| 7 | PUSH 7 | 7 |
| 8 | PUSH 8 | 8, 7 |
| 2 | PUSH 2 | 2, 8, 7 |
| * | POP 2 and 8, compute 8 * 2 = 16, PUSH 16 | 16, 7 |
| 4 | PUSH 4 | 4, 16, 7 |
| / | POP 4 and 16, compute 16 / 4 = 4, PUSH 4 | 4, 7 |
| + | POP 4 and 7, compute 7 + 4 = 11, PUSH 11 | 11 |
| (end) | POP 11 — output result | (empty) |
The final result is 11.
Notice that only operands are pushed onto the stack during evaluation. Operators are never pushed — they are used immediately to combine the two topmost operands.
Why Postfix Evaluation Works So Well
A single left-to-right traversal of a postfix expression is sufficient to evaluate it. This is because operators are already placed correctly according to their precedence — you never need to look ahead or worry about parentheses. The stack naturally handles the order of operations.
Key Points to Remember
- Stacks follow the LIFO (Last In, First Out) principle, which is exactly what postfix evaluation needs.
- In Python, you can implement a stack using a list, with
append()for PUSH andpop()for POP. No explicit TOP variable is needed. …
Drawn by us to help you understand the concept clearly, and verified to make sure it's accurate. For exams, practice from your NCERT textbook's own diagram.
This figure shows how a postfix expression is actually evaluated using a stack — a different, simpler process from Figure 3.3's conversion.
The rule here: every number encountered is pushed onto the stack. Every operator encountered pops the top TWO values off the stack, applies the operator to them, and pushes the single result back on.
Following the postfix expression 7 8 2 * 4 / + left to right: 7, 8, and 2 are pushed one after another. Then * pops the top two values (2 and 8), computes 8 * 2 = 16, and pushes 16 back — leaving the stack with [7, 16]. Next, 4 is pushed. Then / pops 4 and 16, computes 16 / 4 = 4, and pushes 4 back, leaving [7, 4]. Finally + pops 7 and 4, computes 7 + 4 = 11, and pushes 11 back — no …