Reverse Polish Notation: Types of Mathematical Notations & Using A Stack To Solve RPN Expressions

Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Question: Given an array with a sequence that represents a RPN expression, evaluate the Reverse Polish Notation expression.

This is one of those textbook problems. It is a classic expression of when LIFO behaviour is favorable to us when solving certain problems.

To have an RPN expression we need 2 things by definition:

A single digit or series of digits.

It is in the form ["A", "B", "o"] where A and B are integers and o is an operator (either +, -, *, or / ).


Examples:

[ "3", "4", "+", "2", "*", "1", "+" ]

is the same things as ( ( 3 + 4 ) * 2 ) + 1

which is the same things as ( 3 + 4 ) * 2 + 1 because of order of opeartions.

Example 2:

[ "1", "1", "+", "2", "2", "*", "+" ]


Approach

This is a classic stack problem, let us just do this.

The 2 key operations:

When we see a digit we push it to the stack.

When we see an operation we perform 2 pops, apply the operation between the 2 values (first popped item goes on left of the sign, 2nd popped item goes on the right of the sign), and then push the result back onto the stack so we can work with it as we continue.

If it is a valid RPN expression then we should have no problems with mismatches and null pointers, clarify that it is a valid RPN string always with your interviewer.


Complexities

n is the length of the RPN expression

Time: O( n )

We will process all n operators/operands in the expression. Each will either entail an O(1) push/pop or an O(1) arithmetic calculation.

Arithmetic operations take O(1).
Push and pop take O(1).

Space: O( d )

Let d be the total operands (numbers).
Let b be the number of operators (+, -, *, /)

If we have d digits and b operators where d + b = n, we certainly will not use O( d + b ) space (operators are not pushed to the stack).

A worst case is that we have all numbers, followed by the operators. And we will have a stack height of d digits. So we can bound to that.

++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank:    / @hackerrankofficial  

Tuschar Roy:    / tusharroy2525  

GeeksForGeeks:    / @geeksforgeeksvideos  

Jarvis Johnson:    / vsympathyv  

Success In Tech:    / @successintech  

++++++++++++++++++++++++++++++++++++++++++++++++++

This question is number 9.2 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.