Evaluate Reverse Polish Notation
Real-world version: Postfix Tape TotalThe statement here is our own: the same inputs, outputs and technique.
A machinist's paper-tape calculator writes its keystrokes in postfix order: values are typed first, and an operator key is pressed only once both values it will work on already sit on the tape. The finished tape arrives as tokens, one keystroke per entry. An entry is either a whole number in decimal, possibly carrying a minus sign, or one of the four keys "+", "-", "*", "/".
Replay the tape and report the single value that remains when the last keystroke has been handled.
- An operator key takes the two most recently produced values. The one produced earlier is its left operand.
- The divide key drops the fractional part and pulls the quotient toward zero, so a quotient of -3.7 lands on -3.
- Every tape you are given is well formed: each operator key finds two values waiting, no divide key ever meets a zero on its right, and every value produced along the way fits in a signed 32-bit register.
Examples
Example 1
- Input
- tokens = ["5", "2", "-"]
- Output
- 3
The minus key takes 5 as its left operand and 2 as its right, leaving 3 on the tape.
Example 2
- Input
- tokens = ["-7", "2", "/"]
- Output
- -3
A true quotient of -3.5 is pulled toward zero, so the tape keeps -3 rather than -4.
Example 3
- Input
- tokens = ["8", "3", "+", "2", "*", "5", "-"]
- Output
- 17
The tape builds 11, doubles it to 22, then subtracts 5.
Constraints
- 1 <= tokens.length <= 10^4
- Each entry of tokens is one of "+", "-", "*", "/", or a whole number from -200 through 200.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def eval_r_p_n(tokens: list[str]) -> int:public int evalRPN(String[] tokens)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's