Reverse Polish Notation: Types of Mathematical Notations & Using A Stack To Solve RPN Expressions
ฝัง
- เผยแพร่เมื่อ 24 ก.พ. 2019
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: 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. - วิทยาศาสตร์และเทคโนโลยี
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.
where is the code in the description?
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.
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 :)
i dont know how ive found your channel, but thank you for this amazing content!
Welcome. You are appreciated here.
thanks for all this man...for these videos! i appreciate your efforts in teaching....stay blessed
thanks.
Thank you very much :]
Straight forward, easy to understand examples.
Instantly helped me with a coding exercise I was doing
Great explanation, thank you!
Thanks, you explain extremely well
one of the best tutorials i have seen till date !!!. can you please suggest some good programming books and resources.
thx.
This video made the RPN very easy to understand. On my lecture it was way less clear. Thank you, Mister.
Awesome work!! Thank you!!
sure
Your teaching style is too good 👍
Take love from India 🇮🇳
thanks for the video ,awesome work!
This video was immensely helpful. Thank you!
Happy Holidays! Really glad to help 🎉 Do you know about the BacktoBackSWE 5 Day Free Mini Course? Check it out here - backtobackswe.com/
this video was so helpful!
wait i love this guy lmfao hes such a good teacher
Very clear explaination.
Great video, thank you very much! :)
I love your teaching so much
amazing format ! thanks
Glad it was helpful! 😄 Also check out our FREE DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
This is very helpful! Thx
sure
Finally i understand RNP now, thanks a lot!
Thank you! Please enjoy a special code from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=perseusz1691 🎉
Nice explanation!
thx
Thank you
Thank you!
sure
You are the best!
no u
I'm here because I'm Polish lol You're a great teacher. Thank you!
nice and thx
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?
@@hritwiksom3032 no we dont use it lol
I visualize it like Tetris.
The operands are regular blocks.
The operators are 'bombs' that do a specific thing to the blocks below it.
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)?
well one coult use array which would store each term in a expression and use the the array as a stack
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).
nice vid, helpful
love from poland thank you for video
Thank you! Please enjoy a special code from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=antuha-cs4ie 🎉
How would we solve (if possible) a variation of this problem where "+" and "*" can have any number of operands?
Thank you so very muchhhh
Really glad to help 🎉 Do you know about our 5-Day Free DSA Mini Course? Check it out here - backtobackswe.com/
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.
hahaha yeah, i guess
thanks so much, bro
Happy Holidays! Really glad to help 🎉 Do you know about the BacktoBackSWE 5 Day Free Mini Course? Check it out here - backtobackswe.com/
Man YOu are so good
thank you
Thank You, Glad you liked it.
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends :)
Love You.
How can I solve precedence operation using Reverse Polish Notation, if is possible?
Got my A levels tomorrow, thanks man:)
sure
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.
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
@@BackToBackSWE thank you! yeah i'll do mock interviews.
@@kueen3032 great
how did it go? did you get the job?
@@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.
good vid man
thx
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.
ur a G bro!
Ayo the guy explain better than the shit i learn in online classes
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?
2 is the next isdigit thing in the postfix string "34+2*1+"
The thing about RPN, could it be scaled to be used on multiple CPU cores?
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.
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
If I'm reading your question right, that would be written as 22 1 1 + +.
@@a_commenter It's actually 22 1 + 1 +
@@aomafura3374 They do the same thing, since addition is commutative.
Do you have a list of all 250 problems you are going to cover?
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.
@@BackToBackSWE Okay, cool. I'll keep doing popular leetcode problems and watching your videos :)
@@ElfHimSelf 👀👀🔥🔥
Where is link of code in discription
I can't see
The repository is deprecated - we only maintain backtobackswe.com now.
Noted king
but if you solve 3+4*2 the answer should be 11 ?do we need not to consider operator precedence
@@BackToBackSWE ok I understand
@@mukulmalviya1605 nice
What if there are unary operators?
we assume only binary operators
@@BackToBackSWE what about ? : ternary operator
@@Retardsbeeverywhereb dang, jesus u got me
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._
operand operator operation operate operating
교수님보다 잘 설명하시네요 ㅎㅎㅎ
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. :)
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.
Thank fuck I found your channel
hahahahaaha
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
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
Goodbamboo
yeah you can say 3D instead... 👍
reverse flag joke is very funny, though
what, oh haha
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.
Ah yes the Reverse Polish notation, or what I'd like to call the Indonesian notation
where the fuck is the code
Hi, the code is managed on backtobackswe.com/
Petition to rename Reverse Polish Notation as Indonesian Notation
data structures prime newton