Evaluate a Reverse-Polish-Notation Expression

Reported in interviews at Jump Trading

Problem statement

You are given an arithmetic expression in Reverse Polish Notation (RPN) as a list of string tokens. Each token is either an integer literal (a possibly-negative base-10 integer) or one of the four binary operators +, -, *, /. Evaluate the expression and return the resulting integer.

Processing rule: scan left to right; push every integer literal onto a stack; on an operator pop the top two values b (popped first, the right operand) and a (the left operand), push a OP b. Division / is integer division that TRUNCATES TOWARD ZERO (the C/C++ convention), e.g. (-7)/2 == -3 and 7/(-2) == -3. The expression is guaranteed valid (no underflow, no division by zero) and reduces to exactly one value, which you return.

Complete:

rpn_eval(tokens: List[str]) -> int

Example: ['2','1','+','3','*'] is (2+1)*3 = 9.

Show hint

How does postfix notation let you evaluate an expression without worrying about precedence or parentheses?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems