Stack

A stack is LIFO: push and pop at the top of a Python list, underflow when it is empty, and its uses in matching brackets, infix to postfix and evaluating postfix.

Key ideas

LIFO, last in first out: the item pushed most recently is the first one popped, and only the top can be reached.
A Python list works as a stack: push is append(x) and pop is pop(), both at the end, which is the top.
Popping an empty stack is underflow; the textbook’s pop() checks len(s) == 0 first and reports it.
Brackets are balanced if each opening bracket is pushed, each closing one matches the bracket popped, and the stack ends empty.
Infix to postfix: operands go straight to the output; ( is pushed; ) pops up to the matching (; an operator first pops those of equal or higher precedence, then is pushed.
Evaluating postfix: push each number; for an operator pop b, then a, and push a op b; the value left at the end is the answer.

Remember

Push and pop	st = [] st.append(10) st.append(20) print(st.pop()) # 20 print(st) # [10]
Precedence	* and / above + and −; an operator of equal precedence on the stack is popped first
Infix to postfix	A + B * C → ABC+; (A + B) C → AB+C*; A − B + C → AB−C+
Evaluating 5, 3, 2, *, +	push 5, 3, 2; * pops 2 and 3, pushes 6; + pops 6 and 5, pushes 11
Order of operands	the first value popped is the right operand: 8, 2, − gives 8 − 2 = 6
Items left	pushes − pops (an underflow pops nothing)

Watch out

Popping from the bottom: pop() takes the most recent push.
Working out b − a instead of a − b: the first value popped is the right operand.
Pushing an operator without first popping those of equal or higher precedence.
Writing the prefix form (+A*BC) when postfix is asked for.

Worked example

Convert A / B + C / D to postfix using a stack. Show the stack and the output after each symbol. (a) What is the postfix expression? (b) What is the largest number of symbols on the stack at one time?

Working: operands go to the output; ( is pushed; ) pops to the matching (; an operator pops those of equal or higher precedence first

Answer: (a) AB/CD/+; (b) 2