Evaluate Reverse Polish Notation
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 the valid operators are `+`, `-`, `*`, and `/`. Each operand may be an integer or another expression. The division between two integers always truncates toward zero. There will not be any division by zero.
Examples
Constraints
1 <= tokens.length <= 10^4tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
Stack
Approach
Iterate through the tokens. If a token is a number, push it onto a stack. If it is an operator, pop the top two numbers from the stack (the first pop is the second operand, the second pop is the first operand), evaluate the result using the operator, and push the result back onto the stack. Python requires special handling for truncation towards zero during division (using int(a / b) instead of a // b for negative numbers).
Complexity Analysis
This is the standard algorithm for evaluating postfix notation.
class Solution { public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for (String c : tokens) { if (c.equals("+")) { stack.push(stack.pop() + stack.pop()); } else if (c.equals("-")) { int a = stack.pop(); int b = stack.pop(); stack.push(b - a); } else if (c.equals("*")) { stack.push(stack.pop() * stack.pop()); } else if (c.equals("/")) { int a = stack.pop(); int b = stack.pop(); stack.push(b / a); // Java integer division truncates toward zero naturally } else { stack.push(Integer.parseInt(c)); } } return stack.pop(); }}