Reverse Polish Notation and The Stack - Computerphile
HTML-код
- Опубликовано: 20 мар 2014
- Reverse Polish, or Postfix notation is commonly used in Computer Science, particularly in reference to Stacks - but what are stacks and how does postfix work? Professor David Brailsford takes us through it.
Upside Down (Huffman) Trees: • How Huffman Trees Work...
Quick Sort: • Quick Sort - Computerp...
Getting Sorted: • Getting Sorted & Big O...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradychannels
The best part about having a RPN calculator is it will only be borrowed by anyone once and you will always get it back.
Perfect spelling of the Polish name, respect for digging it up.
As a Pole, I'm incredibly impressed by his pronunciation of Łukasiewicz's name.
The key thing to remember here is that not only is this efficient processor wise; RPN is also efficient memory wise. You don't have to keep track of multiple variables all over the place; everything you need to complete your operations is in the stack in the order you are going to have to process them.
It's a very tidy system and a core component of computing that is normally hidden by higher level languages.
Wish i had such a passionate professor at uni, good stuff.
This guy is a phenomenal teacher.
It's very refreshing having a gentleman this age teaching these with this passion! Great teacher! Thank you, sir.
So many of these videos are brilliantly educational that I have started editing and improving the captions for people like myself who are hard-of-hearing or deaf. If you find my changes suitable, please use and alter them as you please. I have so far done this for two videos and intend to continue if you will approve the changes. It is the least I can do for such a great channel. :)
I've always thought the Reverse Polish sounded like a Chess Opening. Which makes it even better.
Too bad I did not find this channel when I was supposed to be studying all this.
It's interesting to watch these coding videos because of the benefits it brings to my own logic. Coding is incredible at showing different ways to do the same thing. Before watching this video, I'd never thought in mathematical terms any different from infix notation. It's incredible to see how that suddenly changes the approach to the entire problem. Long story short, thank you for uploading these, Brady and Sean.
Wonderful video. I first encountered an fell in love with RPN when I got my HP 32SII, back in high school. It was so great. You never needed parentheses and you could enter formulas by reading left to right. So nice to hear Prof. Brailsford explain the history and explain why it was so great.
Brilliant explanation, love this guy.
My first contact with RPN was in a maths exam when I had forgotten my calculator. The teacher was kind enough to let me borrow hers but it was RPN. The first couple of minutes I thought I was as good as dead but I got used to it surprisingly quickly.
I have a calculator app on my tablet that I usually keep in rpn mode. Makes it easier to do bulk operations and it makes sure the calculator doesn't mess up the order of operations.
If you understand this, you pretty much understand everything you need to know to program a language called "Forth". Forth is a brilliant language that is as low level as C (its almost superpowered assembly code) but can be as expressive and powerful as LISP. Its often used for programming very low level stuff, and thus gets called a "toaster language" (Because you might program the chip in a toaster with it). The most astonishing result of forth is;- you can program very very low level stuff without ever needing to set a register.
Damn. One of my assigments is to program a calculator which interprets a string in postfix notation. After watching this video that's an laughably easy task.
Just have to push everything on a stack and I'm as good as done.
I can understand now why they like RPN.
Pretty good pronunciation on Łukasiewicz's name.
Prof Brailsford is great! I'm really enjoying all the Computerphile videos, you've got some great people to talk to, and they're really well edited! Thanks Sean, keep them coming :)
I think this is Professor Brailsford's best Numberphile video yet!
Just saw two videos on this channel and really impressed by the way they go into explaining it by doing into details. The professor is really amazing.
Funny how just the small hint of the title instantly made it clear to me just what the benefit of postfix notation was. I hadn't actually thought about it until now.
I remember when I first learned about this a Comp. Sci. course at uni. The prof. was printing out a tree using a recursive method and just moved the print out statement between different conditions to convey the idea to us. Really cool stuff. :D
Best and most easy to understand explanation I've seen of RPN and stacks. Professor Brailsford always does a good job of breaking things down like this,
I love how passionate this gentleman is about his craft. Great video and quite easy to understand! Thanks Computerphile.
These videos, like the ones about sorting algorithms and huffman trees are my favourite by far on this channel. Keep it up!
I learned about RPN by programming in FORTH on the Redpower computer from the Minecraft mod :)
Brailsford's videos just get better and better. It's like a story unfolding.
A number of years ago I tried learning a programming language that used RPN and couldn't quite understand how it all went together... I wish I had this video back then, it explains things very simply and make sense out of something that has had me confused for over a decade. Thank you professor!
I remember having a similar reaction as Professor Brailsford here when I was first introduced to postfix notation and their relation to stacks. It's just brilliant! Absolutely a match made in heaven :D
I love how you are able simplify really complicated topics. Computerphile... thank you.
Please don't stop filming this wonderful man, and I won't stop watching :]
These videos are so informative. I never leave this channel without learning something new. Great initiative!
You just gave me new confidence to take on Compilers courses. Thank you.
I am so glad you started a podcast with CGPGrey. I had seen your numberphiles videos before and found them interesting but had no idea compterphiles existed until I decided to look at what your many other channels actually are (idea for future pod cast to mention all your channels and what they actually are)As a computer science student I found this very helpful. Thank you!
It's wonderful to see someone as passionate as this gentleman about his professional field
Thanks for this Brady, exam tomorrow.
Evan. glad you liked it - my colleague Sean made this video though... I was just a viewer like you! >Brady
Loved my HP-15 with its RPN and 4 level stack. Many still think it was the best scientific calculator ever made. Enough for Hewlett Packard to put out a limited edition in 2011, *_22 years_* _after the original had been discontinued_! Mine went to silicon heaven after almost 30 years of use. I make do with an RPN calculator on my PC.
I really appreciate you taking the time to make this video. It really encourages me and its super informative.
Thank you! Please do more videos like this.
My compsci professor would always mention the stack but never took the time to explain it, and the book we were using was only focused with teaching the basic semantics of the language. This seems like an important concept to know if you're trying to optimize run time.
These videos are so, so good. Thank you guys for putting them together.
Probably the most interesting video on the channel. Professor Brailsford is very interesting
This is great, I love this guy. I already had a passing understanding of these concepts, but I had no idea they were related.
Whoa, does this man have a playlist or something? What a great teacher! I feel I could watch him for hours and get super smart 😊
Always learning things from Professor Brailsford.
Very nicely explained and awesome demonstration, much appreciated.
Absolutely brilliant explanation, and loved the stacking disks! Keep up the informative videos!
I bet he has them to demonstrate the Tower of Hanoi: en.wikipedia.org/wiki/Tower_of_Hanoi
Amazing explaination and demonstration. Thank you so much for posting this video!
Marvelous way of explaining. Thank you computerphile.
I'm gonna pop some stacks, only got operands in my pocket.
Hello there, i must say, this is one of the best videos i have ever seen on this subject, right now i am studying for a Compiler Design class and i must say, i just loved it, so much clarity, if you are able to, please give my thanks to your colleagues and also thank you, tell them to keep it up
I wish I had such good tutors when I was a student. I enjoy every single one of his videos.
I love listening to this guy talk about literally everything.
I love RPN calculators. They’re so much faster to use, incredibly intuitive once you understand how to use them, it uses less keystrokes, the system runs faster because it doesn’t need to “compile” the code, and nobody ever will want to borrow it after you show them how to use it. 😆
Its like the euler's identity of computer science. Somehow seemingly unrelated conclusions come together in a beautiful way.
Best explanation of RPN and stack I’ve heard yet. 😊
Splendidly explained! My year-long question on how computer determines which operation to be done first has FINALLY been solved.
these videos are brilliant
Brilliant! So illuminating of processes once mysterious to me! Thanks for another great video!
One of the most important videos for any Computer Scientist. The stack is a fundamental data structure.
I love this. when I made a scripting interpreter with compiler in c I used reverse polish notation in my compiled scripts. id never heard of this before today but it made the most sense. especially when parsing nested function calls.
Fantastic! Can't wait to learn more about stacks!!
love you guys computerphile
This was what made reading RPN click for me. Great video.
Brilliant as usual. Reminds me of a friend at the "classes préparatoires" who tried to convince me that his HP stack calculator was way more fitted and nimble than my casio fx 180 P. I couldn't argue and felt a bit clumsy. 30 y. ago, feels like yesterday.
Great explanation and examples.
OMG, I requested this one and they actually made it real. THANK YOU SO MUCH! =D
Love your videos Professor
These videos are great!
Best explanation of this I've ever seen.
i cannot explain how big of a smirk i had when he started talking about loading values into registers, and then using the arithmetic unit... its such a cool process
Oh man, that takes me back to the mid-80s with HP calculators that use RPN and my sophomore data structures class!
Fantastic explanation. Thank you
Will be taking a course on assembly in a week or so, this was a nice introduction. :)
The programming language called Forth, invented by Charles H. Moore has stacks and reverse Polish notation at it's very heart. It's an incredibly powerful and beautifully simple language.
I love this channel.
This was spectacular, thank you!
Really simple yet powerful and effective! great!
I'm a time traveler from 4 years into the future and this is still the best explanation of the subject matter
What a great explanation! :)
Good video! I like the computer science topics, like the trees and stacks and math.
Beautiful video
Thank you soo much for this video ! Helped alot to understand RPN !
Absolutely fantastic
Great video, better than my lecturer by far
thanks for the simplification it was really helpful
Professor Brailsford's pronunciation of "Jan Łukasiewicz" is nearly perfect :) Thank you for that!
A great explanation of stacks and polish notation. Would love to see a follow-up on how things like brackets and unary (negative -) operators work with this.
You don't need brackets as you control precedence by order of the operands and operators For example 4;5;6;+;x might be (5+6)x4, whilst 4;5;+;6;x would be (4+5)x6. Hope you can follow my notation - had to use x as a multiplier as asterisk seems to cause bold type. The system I work with uses semi-colons to indicate a push and then calculates left to right pushing the the result from the last operator back onto the stack.
Yes. I would like to see more of this please. Very interesting.
Thanks Brady :) very simple and cleared my mind on this :) cheers
A lot of the older RPN calculators didn’t use a stack system and instead used 4 registers that just transposed with each other, which was about 2 hz faster (practically null), but it limited you to 4 numbers in the “stack” without needing to use variables. This actually was less limiting than you might expect, but it is nice to have an actual stack that’s limited only to the calculator’s memory.
That was easy to follow, thanks a lot!
I owuld of liked the video to continue the explanation on how it then evaluates (a+b)+c in reverse polish stack notation... but great video, this is something i always wanted to know, how a stack evaluates stuff!
uralic-altaic languages almost always use reverse p. n. word order: like : "i go to school" is "i school to go".
adding at 21: 45 utc+3 : more complex example:
i every day big school to go.
and arabic almost always uses forward p. n. word order:
go i to school big day every.
I was impressed, it was very good pronaunciation of name Łukaszewicz. :)
What a great channel
I remember having to write a program exactly like this in my data structures course. I think my brain was hemorrhaging a little by the time I finished it.
Beautiful explanation :)
Great video! Thanks Prof :D
props to professor Brailsford! very good pronunciation of Łukasiewicz surname