DSA · Stack · #68
Evaluate Reverse Polish Notation
Module 45 · difficulty 3/5·⏱ 30:00starts on first keystroke
You are given an array of strings `tokens` that represents an arithmetic expression in **Reverse Polish Notation** (RPN). Evaluate the expression and return an integer that represents its value. Notes: - The valid operators are `'+'`, `'-'`, `'*'`, and `'/'`. - Each operand may be an integer or another expression. - Division between two integers always **truncates toward zero**. - There will not be any division by zero. - The input is always a valid RPN expression that evaluates to a value fitting in a 32-bit integer. Implement the function `evalRPN(tokens)` that returns the integer result.
Examples
tokens = ["2","1","+","3","*"]→9— ((2 + 1) * 3) = 9tokens = ["4","13","5","/","+"]→6— (4 + (13 / 5)) = (4 + 2) = 6tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]→22— Truncation toward zero applies: 10 * (6 / (-132)) = 10 * 0 = 0, then 0 + 17 + 5 = 22.
Constraints
- · 1 <= tokens.length <= 10^4
- · tokens[i] is either an operator '+', '-', '*', '/', or an integer in the range [-200, 200]
- · The input represents a valid arithmetic expression in RPN
- · Division truncates toward zero; no division by zero occurs
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.