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

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 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.

[@BackToBackSWE]

Table of Contents Weird Flex But Ok (yeah...same shirt too) 0:00 - 0:02 The Problem Introduction 0:02 - 0:23 Different Expression Notations 0:23 - 2:05 Let's Look At Reverse Polish Notation 2:05 - 5:07 Walkthrough With A Stack 5:07 - 6:50 Time Complexity 6:50 - 7:36 Space Complexity 7:36 - 8:36 An abrupt ending because I forgot to do an outro 8:36 The code for this problem is in the description. Fully commented for teaching purposes.

[@BakaDemi]

where is the code in the description?

[@simongrushka983]

as a pole I do apraciate that when you were talking about polish notation you put a proper polish flag but when you were talking about the reverse one you put it upside down :)

[@eladyaniv767]

i dont know how ive found your channel, but thank you for this amazing content!

[@BackToBackSWE]

Welcome. You are appreciated here.

[@janmichaelaustria620]

Thanks for the video my man! I just encountered this problem on LC and I had no idea how to evaluate RPN with pencil and paper.

[@DeadManProp]

I'm here because I'm Polish lol You're a great teacher. Thank you!

[@BackToBackSWE]

nice and thx

[@hritwiksom3032]

So it may sound stupid but I'm curious about one even though it's called polish notation, do you guys actually use it for calculations instead of infix in your day to day life?

[@pseudounknow5559]

@@hritwiksom3032 no we dont use it lol

[@garrettstephens91]

Thanks for the video. I get in RPN how to add, subtract, multiply, and divide single digits together like 5+5 (RPN: 55+). How would you express two or more digits in RPN (like 22+34 or 302 +675)?

[@kaagaj_bottle]

well one coult use array which would store each term in a expression and use the the array as a stack

[@0LoneTech]

You use a separator, e.g. space or Enter. Often the parser will interpret words, as in Forth, but you could also have single keystrokes working on the stack. I.e. 5 could mean if new entry then 5 else 10 * 5 + (the inner step in a left fold parser of decimal numbers). So simply "22 34 +" or "302 675 +" (the space before + is not needed in keystroke calculators).

[@atanusaha8374]

Your teaching style is too good 👍 Take love from India 🇮🇳

[@noapoleon_]

Thank you very much :] Straight forward, easy to understand examples. Instantly helped me with a coding exercise I was doing

[@krazzyfaceoffs]

thanks for all this man...for these videos! i appreciate your efforts in teaching....stay blessed

[@BackToBackSWE]

thanks.

[@nikhilarora7227]

one of the best tutorials i have seen till date !!!. can you please suggest some good programming books and resources.

[@BackToBackSWE]

thx.

[@dominiorrr6510]

This video made the RPN very easy to understand. On my lecture it was way less clear. Thank you, Mister.

[@YourKidnay]

wait i love this guy lmfao hes such a good teacher

[@Jason-tp5cb]

I visualize it like Tetris. The operands are regular blocks. The operators are 'bombs' that do a specific thing to the blocks below it.

[@perseusz1691]

Finally i understand RNP now, thanks a lot!

[@BackToBackSWE]

Thank you! Please enjoy a special code from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=perseusz1691 🎉

[@kueen3032]

Hi! I have seen your videos, they are really great, I found you from a Leetcode thread. My Google interview is scheduled for next month, could you please share your interview experience and give me some tips for the interview. On what topics should i focus more? I've been practicing questions on Leetcode, geeksforgeeks and i do follow your as well as Tushar Roy's videos.

[@BackToBackSWE]

Nice! and I guess all topics? not sure if I can narrow anything since it is really a personal question of what one should study. Just keep doing what you do and do many live interviews

[@kueen3032]

@@BackToBackSWE thank you! yeah i'll do mock interviews.

[@BackToBackSWE]

@@kueen3032 great

[@qaziyahya2818]

how did it go? did you get the job?

[@kueen3032]

@@qaziyahya2818 wasn't able to make through onsite rounds. They contacted me again few weeks ago, for the interviews as the cool down was of 6 months, but I declined politely saying I wasn't prepared enough. The recruiter told me I can apply next year again.

[@isaiahelijah6572]

I love your teaching so much

[@latedeveloper7836]

2:19 What you need to be able to read Reverse Polish Notation 3:30 Perform an operation as soon as you have sufficient operands and an operator 4:05 Text note about last seen items being the first out 4:30 Intro to this problem as a stack 5:10 Start of the stack problem 6:46 Time and space complexity for this expression

[@Nurlanbai]

This video was immensely helpful. Thank you!

[@BackToBackSWE]

Happy Holidays! Really glad to help 🎉 Do you know about the BacktoBackSWE 5 Day Free Mini Course? Check it out here - backtobackswe.com/

[@trumanhw]

Your style of communication (tone, cadence, & even your use of subtleties like pauses) is excellent. Linguistically..? I love a communicator who knows how and when to employ a [well-used] _pause._ Which, to me..? (and even generally..?) Is the operand-equivolent to reading words written that are 'bold & italicized.' A+ As in, if I were reading bold text I could raise my PITCH (not volume) and / or make it steccato ... But bold AND italic? That might require a well-timed pause preceding orrating those _written words._

[@TheChristianmeza97]

Thank you very much for the explanation. Very thorough and clear. EDIT: Just realized all the cuts you did during editing. Very very useful skill and know how to keep viewers engaged in the video.

[@BackToBackSWE]

hahaha yeah, i guess

[@MUmer-jg2uu]

Ayo the guy explain better than the shit i learn in online classes

[@dilushfernando9560]

Got my A levels tomorrow, thanks man:)

[@BackToBackSWE]

sure

[@ElfHimSelf]

Do you have a list of all 250 problems you are going to cover?

[@BackToBackSWE]

yeah, but it is riddled with notes everywhere. I'd love to publish it but to be honest it is basically all very popular questions and famous algorithms.

[@ElfHimSelf]

@@BackToBackSWE Okay, cool. I'll keep doing popular leetcode problems and watching your videos :)

[@BackToBackSWE]

@@ElfHimSelf 👀👀🔥🔥

[@ahcenebelhadi955]

amazing format ! thanks

[@BackToBackSWE]

Glad it was helpful! 😄 Also check out our FREE DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉

[@pixarfilmz4769]

Thanks, you explain extremely well

[@muhammedyilmaz2907]

Very clear explaination.

[@lukasznowarkiewicz]

Great explanation, thank you!

[@bienlizardo6441]

this video was so helpful!

[@Alan-bu2hi]

Wish I had found this in 2019 tears 😭

[@جابرالسهرودي]

This is very helpful! Thx

[@BackToBackSWE]

sure

[@antuha-cs4ie]

love from poland thank you for video

[@BackToBackSWE]

Thank you! Please enjoy a special code from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=antuha-cs4ie 🎉

[@gilbert102]

Awesome work!! Thank you!!

[@BackToBackSWE]

sure

[@orangeshoes]

How would we solve (if possible) a variation of this problem where "+" and "*" can have any number of operands?

[@bjornolsson9103]

Great video, thank you very much! :)

[@jimzhu7654]

You are the best!

[@BackToBackSWE]

no u

[@郭梓梁]

Nice explanation!

[@BackToBackSWE]

thx

[@hey_you_123]

How can I solve precedence operation using Reverse Polish Notation, if is possible?

[@manishmendhekar1973]

Hello Would like to make videos on combination of Stack-Queue with Coding example means 1.Stack+Queue=Queue 2. Queue + Stack=Stack 3.Queue+Queue=Stack 4.Stack+stack=Queue I have faced questions in this combination would please make videos in this topic.

[@natzeni1489]

Thank you

[@ShaliniNegi24]

Thank you!

[@BackToBackSWE]

sure

[@sju9227]

What if there are unary operators?

[@BackToBackSWE]

we assume only binary operators

[@Retardsbeeverywhereb]

@@BackToBackSWE what about ? : ternary operator

[@BackToBackSWE]

@@Retardsbeeverywhereb dang, jesus u got me

[@ayushtiwari6815]

Where is link of code in discription I can't see

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@Mohamed_Hamada_]

thanks so much, bro

[@BackToBackSWE]

Happy Holidays! Really glad to help 🎉 Do you know about the BacktoBackSWE 5 Day Free Mini Course? Check it out here - backtobackswe.com/

[@quintonwilson8565]

nice vid, helpful

[@tinaukabi2394]

I’m kind of confused about how the 2 was added to the first postfix 3 4+ Was the 3 and 4 counted to get the 2 or is 2 added generally?

[@Bdixit]

2 is the next isdigit thing in the postfix string "34+2*1+"

[@kela2812]

What about if I have [22+1+1] then I cant do the operation with +, how can I keep my 22 until I get the other number Thanks

[@a_commenter]

If I'm reading your question right, that would be written as 22 1 1 + +.

[@aomafura3374]

@@a_commenter It's actually 22 1 + 1 +

[@a_commenter]

@@aomafura3374 They do the same thing, since addition is commutative.

[@boriscreativespace]

good vid man

[@BackToBackSWE]

thx

[@abdullateefadeniran-yusuf2214]

Thank you so very muchhhh

[@BackToBackSWE]

Really glad to help 🎉 Do you know about our 5-Day Free DSA Mini Course? Check it out here - backtobackswe.com/

[@jobomathaha9015]

Man YOu are so good thank you

[@BackToBackSWE]

Thank You, Glad you liked it. Do check out backtobackswe.com/platform/content and please recommend us to your family and friends :)

[@panagiotiskyriakou3866]

what about negative numbers ?!?

[@rodrigofilho1996]

The thing about RPN, could it be scaled to be used on multiple CPU cores?

[@0LoneTech]

It describes a serial process, but there's nothing preventing rewriting that into a tree, finding independent branches, and distributing them to separate execution units. Modern CPUs do this with their machine language using register renaming and superscalar out of order execution. The key to parallelism is frequently using higher orders like SIMD or control flow refactoring. We might not have a meaningful parallel form of a small expression, but once you apply it to arrays of data we can partition work in e.g. map or reduce. Futhark is one language specialized in this.

[@trumanhw]

I like that the RPN string / sentence defines the order of operation Execute the symbol's provided. My question though..? handling 2-digit integers that'd (thus far) be ambiguous, ie: 123+2* ... means ..? (12+3)(2) or (1+23)(2) are there space-symbols you can use? (and perhaps axiomatically -- always resolve implicit ambiguities.) Again, I REALLY like your style of communication, tone, and your PAUSES. Linguistically, I find pauses to be like making text 'BOLD or ITALICIZED' if typed.

[@alltheusernamesaregone]

ur a G bro!

[@curtarmmar]

I know this isn’t advanced math by any means but I don’t think I’ll ever be able to deviate from my infix upbringing

[@sofiullah-iqbal-kiron]

Love You.

[@mukulmalviya1605]

but if you solve 3+4*2 the answer should be 11 ?do we need not to consider operator precedence

[@mukulmalviya1605]

@@BackToBackSWE ok I understand

[@BackToBackSWE]

@@mukulmalviya1605 nice

[@trumanhw]

Wait, it's Polish or polished ..? As in, the nation ..? (sincere) (btw, I really like your speaking / communication skills. I'd like to think we do it similarly). :) Thanks I'd just interject the phrase -- what does this CHANGE. :)

[@0LoneTech]

Yes, as in the nation; it was described by a Polish logician named Jan Łukasiewicz, and people aren't confident in remembering, spelling or pronouncing his name. Some languages that use prefix notation extend it to arbitrary arity (e.g. Lisp (+ 1 2 3)), while operations in RPN tend to use fixed arity (1 2 3 + + or 1 2 + 3 +). The use of fixed arity means we never need grouping (whether explicit through parenthesis or implicit through associativity and precedence). RPN is closer to computation order; any operation can only depend on what's to the left.

[@enside8822]

Noted king

[@momotarodadumpling4065]

yeah you can say 3D instead... 👍

[@CamillaHodge-r9n]

Blaise Radial

[@esracigdem2714]

reverse flag joke is very funny, though

[@BackToBackSWE]

what, oh haha

[@minju2871]

교수님보다 잘 설명하시네요 ㅎㅎㅎ

[@floatingfortress721]

operand operator operation operate operating

[@MultiSilverbolt]

Thank fuck I found your channel

[@BackToBackSWE]

hahahahaaha

[@normantuan56]

Ah yes the Reverse Polish notation, or what I'd like to call the Indonesian notation

[@eloeloeloelo8401]

Goodbamboo

[@GlendaPhillips-f8r]

Davis Brian Jones Shirley Wilson Linda

[@DrMuzis]

where the fuck is the code

[@BackToBackSWE]

Hi, the code is managed on backtobackswe.com/

[@andige639]

Petition to rename Reverse Polish Notation as Indonesian Notation

[@GriffithPillow]

data structures prime newton

[@thomasspinthakis2165]

thanks for the video ,awesome work!