Evaluate Postorder Expression Using Stacks
Filed under Microsoft
Free read 2 of 3Understand the input format (list of strings) and the supported set of operators.
The question
Evaluate the value of an arithmetic expression in Reverse Polish Notation (Postfix) using a stack. The expression string contains integers and operators (+, -, *, /).
Constraints
- The given expression is always valid.
- Each operand may be an integer or another expression.
- Division between integers truncates toward zero.
Examples
- Input
- tokens = ["2", "1", "+", "3", "*"]
- Output
- 9
- Why
- ((2 + 1) * 3) = 9
- Input
- tokens = ["4", "13", "5", "/", "+"]
- Output
- 6
- Why
- (4 + (13 / 5)) = 6
Approach
Understand the input format (list of strings) and the supported set of operators.
Repeatedly scan the list to find the first operator, compute the result with adjacent operands, and update the list. Inefficient due to shifting elements.
Use a stack. Iterate through tokens: if it's a number, push to stack; if it's an operator, pop two numbers, apply operator, and push the result back.
Stack underflow from malformed expressions, or single element inputs.
Solution
O(n) time, O(n) space
class Solution:
def evalRPN(self, tokens: list[str]) -> int:
stack = []
for t in tokens:
if t not in "+-*/":
stack.append(int(t))
else:
b, a = stack.pop(), stack.pop()
if t == '+': stack.append(a + b)
elif t == '-': stack.append(a - b)
elif t == '*': stack.append(a * b)
elif t == '/': stack.append(int(a / b))
return stack[0]
Tips
- What they are testing: Test with negative numbers, division by numbers that result in truncation, and single-token expressions.
- Common mistake: Popping operands in the wrong order for non-commutative operations like subtraction and division.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.