You are given an array of strings tokens
that represents an arithmetic expression in a Reverse Polish Notation.
Evaluate the expression. Return an integer that represents the value of the expression.
Note that:
'+'
, '-'
, '*'
, and '/'
.
Example 1:
Input: tokens = ["2","1","+","3","*"] Output: 9 Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = ["4","13","5","/","+"] Output: 6 Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
Constraints:
1 <= tokens.length <= 104
tokens[i]
is either an operator: "+"
, "-"
, "*"
, or "/"
, or an integer in the range [-200, 200]
.This problem involves evaluating an arithmetic expression in Reverse Polish Notation (RPN). RPN, also known as postfix notation, places operators after their operands. This eliminates the need for parentheses and operator precedence rules.
The most efficient way to solve this is using a stack.
Algorithm:
tokens
array.Time Complexity Analysis:
The algorithm iterates through the tokens
array once. Each push and pop operation on the stack takes O(1) time. Therefore, the overall time complexity is O(n), where n is the number of tokens.
Space Complexity Analysis:
The space complexity is determined by the maximum size of the stack. In the worst-case scenario (an expression with many operands before an operator), the stack could hold up to n/2 elements. Thus, the space complexity is O(n).
Code Explanation (Python):
The Python solution efficiently utilizes the operator
module for concise operator handling.
import operator
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
opt = {
"+": operator.add,
"-": operator.sub,
"*": operator.mul,
"/": operator.truediv,
}
s = []
for token in tokens:
if token in opt:
s.append(int(opt[token](s.pop(), s.pop()))) #Note the order here for subtraction and division
else:
s.append(int(token))
return s[0]
The code first defines a dictionary opt
mapping operators to their corresponding functions from the operator
module. It then iterates through the tokens. If a token is an operator, it pops the top two operands from the stack, performs the operation, and pushes the result back. Otherwise (if it's a number), it pushes the number onto the stack. Finally, it returns the single remaining element in the stack. Note the order of s.pop()
in the operator handling. Since we pop from the stack in a LIFO order, the operands will be popped in reverse order, so the order in the operations is important.
Code Explanation (Java):
The Java code uses a Deque
(double-ended queue) to implement the stack.
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stk = new ArrayDeque<>();
for (String t : tokens) {
if (t.length() > 1 || Character.isDigit(t.charAt(0))) {
stk.push(Integer.parseInt(t));
} else {
int y = stk.pop();
int x = stk.pop();
switch (t) {
case "+":
stk.push(x + y);
break;
case "-":
stk.push(x - y);
break;
case "*":
stk.push(x * y);
break;
default:
stk.push(x / y);
break;
}
}
}
return stk.pop();
}
}
The logic is similar to the Python code, but it uses a switch
statement to handle the operators. The Integer.parseInt()
method converts string tokens to integers.
Other languages (C++, Go, TypeScript, Rust, C#) follow similar logic, adapting the stack implementation and syntax to their respective language features. The core algorithm remains the same: use a stack to efficiently evaluate the RPN expression.