Stacks and Monotonic Structures
A stack of operands
Evaluating anything with structure: push values, and let each operator consume what it needs.
Key idea
The evaluation loop
A stack machine reads a sequence of instructions left to right. A value is pushed. An operation pops the arguments it needs, computes, and pushes the result back. When the input runs out, the answer is the single thing left.
This is how a great many real evaluators work, and once the loop is in your fingers it handles anything with the same structure.
Gotcha
The operands come off backward
This is the bug that catches everyone once. The stack returns the most recent value first, so the second operand comes off first.
b, a = stack.pop(), stack.pop() names them in the order they were pushed, so a - b and a / b mean what they look like. Getting this backward is invisible for add and mul, which are commutative, and wrong for sub and div. Test subtraction specifically or you will not notice.
Edge cases
Integer division truncates the wrong way
Python's // rounds toward negative infinity, so -7 // 2 is -4. Most expression evaluators specify truncation toward zero, which would give -3.
When a problem says division truncates toward zero, int(a / b) gives that behavior for the range these problems use. This is the Unit 0 floor-division fact showing up somewhere it actually changes an answer, and it is a genuinely common wrong submission.
Tip
What the stack size tells you
A well-formed program leaves exactly one value. More than one means the input had values nothing consumed; an empty stack when an operator needs arguments means the input was malformed.
Some problems guarantee well-formed input and some ask you to detect malformed input. Read which one you are in, because the guarantee is what decides whether every pop needs a guard.
Predict the output: operand order
Both functions evaluate the same subtraction, and they disagree. Type the two values separated by a space.
Evaluate Reverse Polish Notation
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.