Worksheets › Class 12 › Stack › Cheat sheet
Class 12 Stack: cheat sheet
CBSE Computer Science. 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
Practise Stack
Revise with this page, then practise: every Stack sheet in the app is new, with an answer key and working.
Coming soon for Android and iPhone.