Evaluate Reverse Polish Notation

Try to solve the Evaluate Reverse Polish Notation challenge.

We'll cover the following

Statement#

Given an arithmetic expression in a Reverse Polish Notation (RPN) as an array of strings, tokens, your task is to evaluate and return the value of the given expression.

Points to consider:

  • Valid operators are +, -, *, and /.

  • Each operand can be an integer or another expression.

  • The division between two integers should truncate toward zero.

The given Reverse Polish Notation expression is guaranteed to be valid. This ensures that the expression always evaluates to a result and that there are no division-by-zero operations.

Constraints:

  • 1≤1 \leq tokens.length ≤103\leq 10^3

  • tokens[i] is either an operator (+, -, *, or /) or an integer in the range [−200,200][-200, 200].

Examples#

Created with Fabric.js 3.6.6 Value 9 Input Output Sample example 1 tokens 2 1 + 3 * First, 2 is added to 1, resulting in 3.Then, 3 is multiplied by 3, giving thefinal answer of 9.

1 of 3

Created with Fabric.js 3.6.6 Input Output Value 6 tokens 4 -4 + 6 + Sample example 2 First, 4 is added to -4, resulting in 0.Then, 6 is added to 0, giving the finalanswer of 6.

2 of 3

Created with Fabric.js 3.6.6 Input Output Value 6 tokens 4 13 5 / + Sample example 3 First, 13 is divided by 5, resulting in 2.Then, 4 is added to 2, giving the finalanswer of 6.

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Reverse Polish Notation

1

What does the following arithmetic expression evaluate to?

tokens = [ “33”, “22”, “∗*”, “1111”, “−-” ]

A)

5

B)

-5

C)

19

D)

-19

Question 1 of 30 attempted

Try it yourself#

Implement your solution in the following coding playground.

The optimal solution to this problem runs in O(n) time and takes O(n) space.

Python
usercode > main.py
Input #1
%0 node_01 3 node_11 4 node_21 * node_31 2 node_41 +
Visualization for Input #1
Evaluate Reverse Polish Notation

You might want to go over the Stacks pattern again.

Solution: Basic Calculator

Solution: Evaluate Reverse Polish Notation