DSA problem
Evaluate Reverse Polish Notation
You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation (a.k.a. postfix notation). Evaluate the expression and return an integer that represents its value.
Note the following rules: the valid operators are +, -, *, and /; each operand may be an integer or another expression; the division between two integers always truncates toward zero (so 6 / -132 is 0, not -1); there will not be any division by zero; the input represents a valid arithmetic expression; and the answer and all intermediate calculations fit in a 32-bit integer.
Reverse Polish Notation places the operator after its operands, which conveniently eliminates the need for parentheses. For example, the infix expression ((2 + 1) * 3) becomes the RPN ["2", "1", "+", "3", "*"]. The defining property of RPN is that it can be evaluated linearly with a single stack — no parser, no recursion, no precedence rules required.
The algorithm walks left to right through the tokens. If a token is a number, push it onto a stack of integers. If it is an operator, pop the top two values (the right operand is popped first, the left operand second), compute the result, and push it back. After the entire sequence is consumed, the stack holds exactly one value: the answer. This is O(n) time and O(n) space, where n is the number of tokens.
Examples
tokens = ["2","1","+","3","*"]9tokens = ["4","13","5","/","+"]6tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]22Constraints
- 1 <= tokens.length <= 10^4
- tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.