Evaluate an expression in Reverse Polish Notation. Valid operators are +, -, *, and /. Each operand may be an integer or another expression. Division between two integers always truncates toward zero.
tokens = ["2","1","+","3","*"]9tokens = ["4","13","5","/","+"]6+, -, *, /stack, scan tokens left→rightstack.push(parseInt(t))b = stack.pop(), a = stack.pop()a OP b, push result back onto stackstack.pop() — the single remaining elementRPN (postfix notation) is designed for stack evaluation. Operands wait on the stack until their operator arrives. When an operator appears, it always applies to the two most recent values — no parentheses or precedence rules needed. Stack size is at most O(n/2) for a balanced expression.
Converting it back to normal notation with brackets is slow and complicated. The notation is designed to be evaluated with a stack.
Read the tokens left to right. Push every number onto the stack. For an operator, pop two numbers, apply it, and push the result. Be careful with order: the first number popped is the right operand.
Operands go on the stack, operators pop two and push one. The first pop is the right operand.
Run the animation above on your own input, or watch the 1:11 video explanation of Evaluate Reverse Polish Notation with a dry run and Java code.