Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Expression Evaluation (RPN/Infix) subpattern.

Problem statement

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.

- The input represents a valid arithmetic expression in a reverse polish notation.

- The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

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

Example 2:

Input: tokens = ["4","13","5","/","+"] Output: 6 Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","","/","","17","+","5","+"] Output: 22 Explanation: ((10 (6 / ((9 + 3) -11))) + 17) + 5 = ((10 (6 / (12 -11))) + 17) + 5 = ((10 (6 / -132)) + 17) + 5 = ((10 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22

Constraints:

- 1 <= tokens.length <= 104

- tokens[i] is either an operator: "+", "-", "", or "/", or an integer in the range [-200, 200].

Topics and companies

Topics: Array, Math, Stack.

Reported in interviews at Amazon, Oracle, LinkedIn, Google, Microsoft.

How to practise Evaluate Reverse Polish Notation on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n), where n is the number of tokens. Each token is processed exactly once. time and O(n), where n is the number of tokens. In the worst case (all operands), the stack can grow to size n. space.

Open Evaluate Reverse Polish Notation in the code editor, or read the Evaluate Reverse Polish Notation editorial for a worked solution with its approach and complexity analysis.

Where Evaluate Reverse Polish Notation sits in the DSA pattern sheet

Problems related to Evaluate Reverse Polish Notation

Other problems that use the same Expression Evaluation (RPN/Infix) and Stack Patterns techniques:

Preparing this workspace.