Assertion (A): A postfix expression never needs parentheses to show the order in which its operations are performed. Reason (R): In postfix notation the position of each operator relative to its operands fixes the order of evaluation.

Both A and R are true, and R is the correct explanation of A

Both A and R are true, but R is not the correct explanation of A

Stack

A pile of plates is used from the top: the plate put on last is the first one taken off. A stack is the data structure built on exactly that rule, and it turns up wherever the most recent thing must be dealt with first — the undo button, the browser's back button, matching brackets, and the way a computer evaluates arithmetic. This chapter defines the stack and its two operations, implements it with a Python list, and then works through the paper's favourite stack questions: tracing a sequence of pushes and pops, converting infix expressions to postfix, and evaluating postfix expressions step by step.

What a Stack Is: Last In, First Out

A stack is a linear data structure in which elements are added and removed at one end only, called the TOP. Because the element added last is always the first to be removed, a stack follows the LIFO principle — Last In, First Out. Adding an element is PUSH; removing the top element is POP. Trying to push onto a stack that is already full is overflow; trying to pop from an empty stack is underflow. A Python list grows as needed, so overflow does not arise in practice there, but underflow does and must be checked before every pop.

Reversing a string or list: push every element, then pop them all — they come out in reverse order.
Undo and redo in a text editor: each change is pushed, and undo pops the most recent one.
The browser back button: each page visited is pushed, and back pops to the previous page.
Matching parentheses: push each opening bracket, pop one for each closing bracket; the expression is balanced if no pop finds the stack empty and the stack is empty at the end.

A Stack in Python

A Python list makes a natural stack if its end is treated as the top: append(x) pushes and pop() (with no argument) removes and returns the last element. The book builds the operations as small functions — isEmpty returns len(stack) == 0, size returns len(stack), top (also called peek) returns stack[-1] without removing it, and display prints the elements from the top down. Each function that pops or peeks first checks isEmpty, which is how underflow is avoided.

Reversing a word with a stack — this prints KCATS:
s = []
for ch in "STACK":
s.append(ch)
r = ""
while s:
r += s.pop()
print(r)

🧠 Tracing pushes and pops

Write the stack as a list with the top on the right and update it after every operation. Push 5, push 8, pop, push 3, push 9, pop, pop: [5] → [5, 8] → [5] (8 out) → [5, 3] → [5, 3, 9] → [5, 3] (9 out) → [5] (3 out). The elements come out as 8, 9, 3 and 5 is left.

Infix, Prefix and Postfix Notation

We normally write the operator between its operands — infix notation, as in A + B. Infix needs precedence rules and parentheses to say what is done first: in A + B * C the multiplication happens first, and (A + B) * C forces the addition first. Two other notations put the operator elsewhere. In prefix (Polish) notation the operator comes before its operands: + A B. In postfix (reverse Polish) notation it comes after them: A B +. Postfix and prefix need no parentheses at all, because the position of each operator already fixes the order of evaluation — which is why computers convert to postfix before evaluating.

The same expressions in three notations
Infix	Prefix	Postfix
`A + B`	`+ A B`	`A B +`
`A + B * C`	`+ A * B C`	`A B C * +`
`A * B + C`	`+ * A B C`	`A B * C +`
`(A + B) * (C - D)`	`* + A B - C D`	`A B + C D - *`
`A - B + C`	`+ - A B C`	`A B - C +`

Converting Infix to Postfix, and Evaluating Postfix

Infix to postfix — the stack holds operators. Scan the infix expression from left to right. An operand goes straight to the output. A left parenthesis is pushed. A right parenthesis pops operators to the output until the matching left parenthesis, which is popped and discarded. An operator first pops to the output every operator on top of the stack with higher or equal precedence, then is pushed itself. When the scan ends, pop whatever remains onto the output. For A + B * C: A out; + pushed; B out; * has higher precedence than +, so it is pushed on top; C out; end — pop * then +, giving A B C * +.

Evaluating postfix — the stack holds operands. Scan from left to right. Push each operand. On an operator, pop two values — the first popped is the right operand, the second the left — apply the operator and push the result. At the end exactly one value remains, the answer. For 6 2 3 + * 4 -: push 6, 2, 3; + pops 3 and 2 and pushes 5 → [6, 5]; * pops 5 and 6 and pushes 30; push 4; - pops 4 and 30 and pushes 30 − 4 = 26.

⚠️ Order matters for − and /

In 8 2 / the first value popped is 2 and the second is 8, so the operation is 8 / 2 = 4, not 2 / 8. Reversing the two operands changes nothing for + and *, which is exactly why the paper sets its evaluation questions with − and /.

Key takeaways

A stack adds and removes at one end, the TOP, so it is LIFO; PUSH adds, POP removes the top.
Pushing onto a full stack is overflow; popping an empty stack is underflow — check isEmpty before every pop.
With a Python list as a stack, append() pushes, pop() pops and stack[-1] peeks at the top.
Stacks reverse data, power undo and the back button, and check that brackets are balanced.
Prefix puts the operator first, postfix last; neither needs parentheses. A + B * C is A B C * + in postfix.
In conversion the stack holds operators; in evaluation it holds operands, and the first value popped is the right operand.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

What is the output of the following code?
s = []
for ch in "STACK":
s.append(ch)
r = ""
while s:
r += s.pop()
print(r)
1. STACK
2. KCATS
3. K
4. SKCAT
Show answer
Answer: B — KCATS
The loop pushes S, T, A, C, K, leaving K on top; the while loop then pops until the list is empty, taking K first and S last, so r becomes KCATS — a stack reverses whatever passes through it. STACK would need first-in-first-out removal, which is a queue, and K alone forgets that the while loop keeps popping until the stack is empty.
What is the postfix form of the infix expression A + B * C?
1. A B + C *
2. A B C + *
3. + A * B C
4. A B C * +
Show answer
Answer: D — `A B C * +`
Multiplication outranks addition, so B * C is formed first and written B C *; adding A to that result gives A B C * +. A B + C * is the postfix of (A + B) * C, the reading that ignores precedence. + A * B C is a correct form of the same expression, but in prefix notation, not postfix.
Convert the infix expression (A + B) * (C - D) to postfix.
1. A B + C D - *
2. A B C D + - *
3. * + A B - C D
4. A B + * C D -
Show answer
Answer: A — `A B + C D - *`
Each bracket becomes a unit first: A + B is A B + and C - D is C D -; the * joining them comes after both, giving A B + C D - *. The prefix form * + A B - C D is correct notation of the wrong kind. Writing * between the two halves is still thinking in infix, and gathering all four operands before any operator changes which values each operator combines.
Using a stack, evaluate the postfix expression 6 2 3 + * 4 -
1. 14
2. -26
3. 26
4. 8
Show answer
Answer: C — 26
Push 6, 2 and 3; + pops 3 and 2 and pushes 5; * pops 5 and 6 and pushes 30; push 4; - pops 4 then 30 and computes 30 − 4 = 26. The answer −26 subtracts in the order the values were popped, 4 − 30, forgetting that the first value popped is the right operand. 14 comes from multiplying 6 by 2 before the addition has been done.
On an empty stack the operations push(5), push(8), pop(), push(3), push(9), pop(), pop() are performed in that order. In what order do the elements come out?
1. 8, 3, 9
2. 8, 9, 3
3. 5, 8, 3
4. 9, 3, 5
Show answer
Answer: B — 8, 9, 3
After 5 and 8 are pushed, the first pop removes 8; 3 and 9 are then pushed on top of 5, so the next two pops remove 9 and then 3, leaving 5 on the stack. The order 8, 3, 9 removes the later items in the order they arrived, which is queue behaviour, and 5, 8, 3 starts from the bottom of the stack instead of its top.
What is the condition called when a program tries to pop an element from an empty stack?
1. Overflow
2. Collision
3. Underflow
4. Deadlock
Show answer
Answer: C — Underflow
Removing from a stack that holds nothing is underflow, and a stack function avoids it by checking isEmpty before popping. Overflow is the opposite case, pushing onto a stack that is already full. Collision is a hashing term for two keys landing in one slot, and deadlock describes processes waiting on each other — neither is a stack condition.
Assertion (A): A postfix expression never needs parentheses to show the order in which its operations are performed. Reason (R): In postfix notation the position of each operator relative to its operands fixes the order of evaluation.
1. Both A and R are true, and R is the correct explanation of A
2. Both A and R are true, but R is not the correct explanation of A
3. A is true, but R is false
4. A is false, but R is true
Show answer
Answer: A — Both A and R are true, and R is the correct explanation of A
In postfix an operator acts on the two values immediately before it on the stack, so where it stands decides when it is applied — A B + C * and A B C * + mean different things without any brackets. That positional rule is the reason parentheses are unnecessary, so R explains A. Choosing "R is not the explanation" overlooks that precedence and brackets are exactly what the position replaces.
What is printed by the following code?
stack = [10, 20, 30]
stack.append(stack.pop() + stack[-1])
print(stack)
1. [10, 20, 30, 60]
2. [10, 50]
3. [10, 20, 60]
4. [10, 20, 50]
Show answer
Answer: D — `[10, 20, 50]`
Python evaluates the left operand first: stack.pop() removes and returns 30, leaving [10, 20], so stack[-1] is now 20; their sum 50 is appended, giving [10, 20, 50]. The answer with 60 reads stack[-1] as 30, as if the pop had not yet happened. Keeping 30 in the list forgets that pop removes the element, and [10, 50] removes 20 as well, which peeking with [-1] never does.