Evaluate Reverse Polish Notation

Medium · Stack

You are given a list of strings representing an arithmetic expression written in postfix (reverse Polish) notation. Each token is either an integer or one of the operators +, -, *, /. Scan the tokens left to right, applying each operator to the two most recently seen numbers, and return the final computed integer result. Division between two integers should truncate toward zero.

Examples

Input:  tokens = ["2","1","+","3","*"]
Output: 9
Why:    (2 + 1) * 3 = 9

Input:  tokens = ["4","13","5","/","+"]
Output: 6
Why:    13 / 5 truncates to 2, then 4 + 2 = 6

Input:  tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Why:    Evaluating step by step following postfix order yields 22

Constraints

1 <= tokens.length <= 10^4, each token is an integer in [-200, 200] or one of +, -, *, /, and the expression is always valid with no division by zero

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Evaluate Reverse Polish Notation

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Evaluate Reverse Polish Notation. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.