Evaluate Reverse Polish Notation: One Stack and Three Gotchas
Linkjob AIEvaluate Reverse Polish Notation looks like a warm-up, and it is, but it hides three details that separate a clean answer from a buggy one: operand order, integer division toward zero, and recognising negative numbers.
Why a stack fits
In postfix notation every operator applies to the two most recent values that have not been consumed yet. That is exactly last-in, first-out, so push numbers and, on an operator, pop two values, combine them and push the result. When the tokens run out, the single value left is the answer.
Code (Python)
def eval_rpn(tokens):
stack = []
for t in tokens:
if t in ('+', '-', '*', '/'):
b = stack.pop()
a = stack.pop()
if t == '+': stack.append(a + b)
elif t == '-': stack.append(a - b)
elif t == '*': stack.append(a * b)
else: stack.append(int(a / b))
else:
stack.append(int(t))
return stack[0]Gotcha 1: operand order
The first value you pop is the right operand. For tokens ["4", "13", "5", "/", "+"] you must compute 13 / 5, not 5 / 13. Popping into b first and a second makes the order obvious when you read the code back.
Gotcha 2: division truncates toward zero
The problem asks for truncation toward zero. In Python, -7 // 2 is -4 because floor division rounds down, so use int(a / b) instead. In Java and C++ plain integer division already truncates toward zero. Saying this out loud is an easy signal that you know your language.
Gotcha 3: negative numbers
A token like "-11" is a number, not an operator. Checking membership in the operator set, rather than looking at the first character, handles it for free.
Complexity and follow-ups
Each token is processed once, so time is O(n) and the stack holds at most O(n) values. Common follow-ups are converting infix to postfix with the shunting-yard algorithm and Basic Calculator, where the same stack idea handles parentheses.
Disclosure: I work on Linkjob AI. If you want hints like these while you practise live coding, our AI interview copilot is free to try.