Evaluate an expression written in reverse Polish notation. Each operator comes after its two operands, so there are no brackets.
DSA Animator › DSA Revision › Stack › Evaluate Reverse Polish Notation
Remember: operands go on the stack, operators pop two and push one. The first pop is the right operand. The video solves Evaluate Reverse Polish Notation (LeetCode 150, Medium) with the Stack pattern from the Stack topic, and you can replay every step in the interactive Evaluate Reverse Polish Notation animation.
Evaluate an expression written in reverse Polish notation. Each operator comes after its two operands, so there are no brackets.
The tokens 2, 1, plus, 3, times mean 2 plus 1, then times 3. The answer is 9.
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.
Push 2. Push 1. Plus pops 1 and 2, and pushes 3. Push 3. Times pops 3 and 3, and pushes 9. One number is left: the answer is 9.
In code, loop over the tokens. For an operator, pop b, then a, and push a operator b. Otherwise, parse the token as a number and push it. Return the last value, so it's O of n time and O of n space.
Remember: operands go on the stack, operators pop two and push one. The first pop is the right operand.