Reverse Polish Notation and The Stack - Computerphile

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

[@duckrutt]

The best part about having a RPN calculator is it will only be borrowed by anyone once and you will always get it back.

[@Jarzyniak]

As a Pole, I'm incredibly impressed by his pronunciation of Łukasiewicz's name.

[@tomasznikiel2508]

Perfect spelling of the Polish name, respect for digging it up.

[@thesnowedone]

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.

[@vagramAU]

Wish i had such a passionate professor at uni, good stuff.

[@jamestaylor7974]

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. :)

[@IMortage]

I've always thought the Reverse Polish sounded like a Chess Opening. Which makes it even better.

[@ArnavDhamija]

This guy is a phenomenal teacher.

[@mikelipsey8837]

It's very refreshing having a gentleman this age teaching these with this passion! Great teacher! Thank you, sir.

[@Karthik-yy6up]

Too bad I did not find this channel when I was supposed to be studying all this.

[@wattage]

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.

[@Chaosdude341]

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.

[@unvergebeneid]

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.

[@shayneoneill1506]

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.

[@angeldude101]

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.

[@MrAntiKnowledge]

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.

[@JAN0L]

Pretty good pronunciation on Łukasiewicz's name.

[@aries_9130]

Brilliant explanation, love this guy.

[@fuzzylilpeach6591]

Its like the euler's identity of computer science. Somehow seemingly unrelated conclusions come together in a beautiful way.

[@Ostsol]

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.

[@thenorup]

I learned about RPN by programming in FORTH on the Redpower computer from the Minecraft mod :)

[@Ghost00117]

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

[@JimCullen]

I think this is Professor Brailsford's best Numberphile video yet!

[@IceDave33]

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 :)

[@GogiRegion]

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. 😆

[@LimeGreenTeknii]

I'm gonna pop some stacks, only got operands in my pocket.

[@Fhuaran]

Brailsford's videos just get better and better. It's like a story unfolding.

[@AstroTorch]

Thanks for this Brady, exam tomorrow.

[@Computerphile]

Evan. glad you liked it - my colleague Sean made this video though... I was just a viewer like you! >Brady

[@vivianrichards3434]

You just gave me new confidence to take on Compilers courses. Thank you.

[@KaiserSpherical]

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

[@intermarer9145]

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 😊

[@krishnaindani8414]

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.

[@NotMarkKnopfler]

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.

[@Grngnak]

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!

[@esra_erimez]

I'm a time traveler from 4 years into the future and this is still the best explanation of the subject matter

[@ElectiveTool]

Please don't stop filming this wonderful man, and I won't stop watching :]

[@BlakeHelms]

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,

[@peterlilliegeo]

I love how passionate this gentleman is about his craft. Great video and quite easy to understand! Thanks Computerphile.

[@goodguy686]

These videos, like the ones about sorting algorithms and huffman trees are my favourite by far on this channel. Keep it up!

[@ozymet]

I love how you are able simplify really complicated topics. Computerphile... thank you.

[@WinBear]

Oh man, that takes me back to the mid-80s with HP calculators that use RPN and my sophomore data structures class!

[@aquere]

It's wonderful to see someone as passionate as this gentleman about his professional field

[@anakso]

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!

[@StankyPickle1]

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.

[@kaptenrobert]

These videos are so informative. I never leave this channel without learning something new. Great initiative!

[@BrendonWilliams]

This was what made reading RPN click for me. Great video.

[@MattBrookes1304]

Probably the most interesting video on the channel. Professor Brailsford is very interesting

[@RMoribayashi]

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.

[@QDinar]

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.

[@XNAforyou]

One of the most important videos for any Computer Scientist. The stack is a fundamental data structure.

[@sydniusalminia5364]

I really appreciate you taking the time to make this video. It really encourages me and its super informative.

[@JohnJohnson-xt7zf]

I love listening to this guy talk about literally everything.

[@Urahara12]

Absolutely brilliant explanation, and loved the stacking disks! Keep up the informative videos!

[@unvergebeneid]

I bet he has them to demonstrate the Tower of Hanoi: en.wikipedia.org/wiki/Tower_of_Hanoi

[@ericmiller3231]

These videos are so, so good. Thank you guys for putting them together.

[@Spender604]

Always learning things from Professor Brailsford.

[@AaronPaden]

This is great, I love this guy. I already had a passing understanding of these concepts, but I had no idea they were related.

[@woonsuen545]

Splendidly explained! My year-long question on how computer determines which operation to be done first has FINALLY been solved.

[@ApostolisTympakianakis]

I wish I had such good tutors when I was a student. I enjoy every single one of his videos.

[@ntfsguy3601]

Best explanation of RPN and stack I’ve heard yet. 😊

[@yellownexusoftheworlds8646]

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

[@bazsturgeon3017]

Very nicely explained and awesome demonstration, much appreciated.

[@adelahmed5886]

Marvelous way of explaining. Thank you computerphile.

[@GogiRegion]

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.

[@evatokkallos5723]

Amazing explaination and demonstration. Thank you so much for posting this video!

[@flemish4]

these videos are brilliant

[@LimitedWard]

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.

[@MrCanigou]

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.

[@valseedian]

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.

[@conkerconk3]

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

[@bruinflight1]

Brilliant! So illuminating of processes once mysterious to me! Thanks for another great video!

[@mosesnah2893]

love you guys computerphile

[@AlexMaday]

Fantastic! Can't wait to learn more about stacks!!

[@CusterFlux]

Best explanation of this I've ever seen.

[@MichailShaposhnikov]

OMG, I requested this one and they actually made it real. THANK YOU SO MUCH! =D

[@mbalicki]

Professor Brailsford's pronunciation of "Jan Łukasiewicz" is nearly perfect :) Thank you for that!

[@connorbunch3577]

Great explanation and examples.

[@Maxflay3r]

Wuh-kah-shye-veech with the accent on wuh. The "shye" is a bit different, but i can't think of anything in english that would use the intended sound. It's kind of a merge between a "sh" and a "see".

[@DudokX]

Really simple yet powerful and effective! great!

[@Pedritox0953]

Love your videos Professor

[@Dayanto]

Will be taking a course on assembly in a week or so, this was a nice introduction. :)

[@ThomasGiles]

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.

[@Beer_Dad1975]

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.

[@xxPow3rslave]

I love this channel.

[@cyprinus]

These videos are great!

[@hm6052]

Fantastic explanation. Thank you

[@coreyredmon5611]

Yes. I would like to see more of this please. Very interesting.

[@AndrewBlundon]

Excellent. I've been waiting for this one, I suggested it last year as a topic for Numberfile. RPN takes a while to learn but once you get it things become so much easier.... I'd be lost without my HP48G calculator (which doesn't have an "=" button but has an "ENTER" button instead).

[@batsali99]

I've had a HP50G for 4 years now. I'm so much used to RPN notation that I have trouble using "normal" calculators with any efficiency :D RPN is a much faster and error proof way to tackle hairy expressions. RPN users unite! :D

[@seth094978]

batsali99 I had my first taste of programming on a 28S, and ever since then I haven't been able to get away from RPN. I now own two 50G's and a 35S. I love how "=" is a secondary function. It really discourages people from "borrowing" my calculators.

[@batsali99]

seth094978 Yeah, the borrowing thing is quite true :)

[@tobias-edwards]

Great video, better than my lecturer by far

[@mcvoid1]

Good video! I like the computer science topics, like the trees and stacks and math.

[@DoctorDARKSIDE]

This was spectacular, thank you!

[@sureshseneviratne1841]

Thank you soo much for this video ! Helped alot to understand RPN !

[@SallowDawn]

Beautiful video

[@666Tomato666]

props to professor Brailsford! very good pronunciation of Łukasiewicz surname

[@KristoffDoe]

I was impressed, it was very good pronaunciation of name Łukaszewicz. :)

[@amigojapan]

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!

[@TheLadyApollo]

Absolutely fantastic

[@karimkohel3240]

thanks for the simplification it was really helpful

[@magnusmaynard]

What a great explanation! :)

[@philipmifsud1638]

Thanks Brady :) very simple and cleared my mind on this :) cheers

[@user-le3tu8pq7e]

What a great channel

[@GeoffreyBernardo]

Very good lecture! LISP languages use the opposite: forward polish notation. There parentheses are required to show where the list of operands end for a operator.