Back to DSA

Evaluate Reverse Polish Notation

medium
Acceptance: 46%
StackMath

You are provided with a list of string tokens that encode a mathematical expression in postfix (Reverse Polish) form. Compute and return the integer result of evaluating this expression. The supported operators are addition (+), subtraction (-), multiplication (*), and division (/). Operands are integers or sub-expressions, and integer division must round toward zero.

Examples

Example 1:
Input:tokens = ["3","4","+","2","*"]
Output:14
Example 2:
Input:tokens = ["5","12","4","/","+"]
Output:8

Hints

Related Problems

Min StackmediumValid ParentheseseasyDaily TemperaturesmediumNext Greater Element IeasyAsteroid Collisionmedium
00:00
import java.util.*;

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String t : tokens) {
            if ("+-*/".contains(t)) {
                int b = stack.pop(), a = stack.pop();
                switch (t) {
                    case "+": stack.push(a + b); break;
                    case "-": stack.push(a - b); break;
                    case "*": stack.push(a * b); break;
                    case "/": stack.push(a / b); break;
                }
            } else {
                stack.push(Integer.parseInt(t));
            }
        }
        return stack.pop();
    }
}
Time complexityO(n)
Space complexityO(n)