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.
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. :)
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.
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.
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
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
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.
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,
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 :)
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.
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.
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.
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!
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.
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.
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.
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.
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 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
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).
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
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.
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.
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. 😆
This seems such a cooler notation than the standard one. Especially in computing it gets incredibly confusing with operands. Some have higher priority, some go right to left some left to right amd stuff...
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.
Great video. This is as good an explanation of RPN as I have ever seen. RPN is especially useful when dealing with computers because it lays out the information in the same way the machine has to use it. It is however not great for non machines like humans. We do not use the information the same way a machine does. We see the entire line at once and then evaluate it. It is why I prefer TI calculators over HP calculators. I prefer to let the machine evaluate then execute the line. That makes life simpler for me. I really do not care if it is simpler for the machine. I would recommend an HP calculator for anyone going into Computer Science or Engineering because these two disciplines require such heavy use of computers and writing original code it is useful in thinking in these program steps to begin with.
Not trying to start an argument, pun intended, but RPN is more natural than you think. If when you were being taught arithmetic they taught you to arrange your numbers vertically, you were using RPN. The dawn of the digital calculator actually caused a lot of confusion. TI's follow the throwback that early calculators only had three registers since only one operand could be preformed at a time. HP's stack flow is an analog to the conventional vertical 'pen and paper' method.
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.
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.
I have a modern scientific calculator which only gets used for some of the more advanced calculations I need to do when I'm not at my computer. But it is so much faster and easier to deal with complicated equations using a RPN calculator, as you type the values in the same order you would if you were solving it yourself. Now that you can get RPN calculator applications for cell phones, and not have to fork out a load of money, doing calculations couldn't be easier.
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!
I always like presenting prefix/infix/postfix via binary trees when teaching people how to translate them. for example if you build a binary tree of the equation "a+b*c", where operands are leaves and operators are nodes, you'd get a tree that looks like this. ( + ) / \ ( a ) ( * ) / \ ( b ) ( c ) Now take your finger and start directly above the root of this tree. Draw an outline counter-clockwise around the tree hugging all the leaves and nodes. if you want to write this tree in prefix simply write down the node/leaf whenever your finger passes directly to the left of it. For infix is when you passes directly below one. And for postfix is when you pass directly to the right of one. In the end you would get these results prefix: +a*bc infix: a+b*c postfix: abc*+
Just as the tree mentioned in this video, a stack is an abstract data type. A heap, however, isn't. Just because the stack known from memory management is known as _the_ _stack_ in that context doesn't make it special as far as stacks go. The more likely next step from here is the queue, since a stack is also called LIFO (last in, first out) and a queue is called FIFO (first in, first out). So you're talking about a totally different branch of computer science called computer engineering. That doesn't mean that this won't be covered some day but they are currently just laying the groundwork for this with stuff that's essential in _all_ areas of computer science.
Penny Lane Science != Engineering. Science is research-oriented, engineering is the application of science to solve problems within some economic scope. Engineering, thus, cannot be a branch of science. Also, "the stack" is extraordinarily special; as a data structure, it's LIFO, but it's singularly important because without it, contemporary, register-based CPUs cannot perform subroutine calls recursively. Whether implemented in hardware (as on x86) or in software (as on PowerPC and most other RISCs), "the stack" is absolutely vital for ... everything. "The heap", however, is not "a heap" (usually), and so you're right to say it's not an abstract data type. However, it, nonetheless, remains vitally important, for it is the pool of memory from which stacks for processes and other data structures are typically allocated from. I say typically because there is one language, Forth, which generally lacks a heap in this fashion. But, I digress.
Samuel Falvo II Consider quite a lot of computing research is funded by outside companies, many research projects are actually elaborating on new applications of computing. Same goes for non-academic companies like Google, which come up with new large-scale algorithms and can be considered science. I would say in field of computing, engineering and science are inseparable.
Samuel Falvo II Ok, replace "computer science" with "informatics" which is the name given to computer science in about any other language except English. If your argument still holds, then at least we aren't just arguing semantics. I had hoped I made clear that I do not doubt that memory management is a worthy topic for videos to come but that this is totally besides the point. And the point is that Jordan Stocker apparently jumped to conclusions because he had heard "stack" in a very specialized context which probably kept him from seeing the bigger picture here and the fundamental importance of "stack" as an ADT and a concept. Now if you want to talk to me about that then please do, otherwise I'm afraid this discussion lacks the focus to keep me engaged. Oskar Mamrzynski A heap, which has got nothing to do with _the_ heap as Samuel rightly said, is a data structure but _not_ an abstract data type. The abstract data type implemented using heaps is called "priority queue".
Wouldn't bc*a+ be more "stack efficient" than abc*+? Using the latter three items need to be pushed before the calculation begins, with the former there's only ever two items on the stack.
Some operators might not be commutative. (think about multiplying matrices)
10 лет назад+1
I don't think efficiency was the point here. Using abc*+ demonstrates how you can have more than two operands on the stack and how they are evaluated. Had he used bc*a+, people might have gotten the wrong idea that there must always be at most two operands on the stack(since the second example also had two)
But you'd have to search for that event in the arguments you are entering, it's much easier to go from the start to the end with that kind of thing. It saves a lot of time. Imagine you have a very long 100+ arguments operation to do ...
Tom Furie That still doesn't mean that you can just swap the operands around. Matrices are only one example. If you are using lists and you want to concatenate them, the order of operands is obviously very important. (Lisp and Haskell come to mind, even though they use prefix instead of postfix) The stack is only used for keeping your data around in a simple way. It's not used for the calculations themselves, which are completely irrelevant. Additionally, you don't have to keep the variables themselves on the stack. You could also just use pointers, which allows you to mix objects from base classes and derived classes without any hassle with object size etc.
I remember being very frustrated about writing in FORTH because it was a stack based language and the specific compiler I was using didn't allow you to make changes, you had to type everything right at ONCE! I tried 5 hours to make something that would have taken 30 minutes in LUA. ahh good days.
This could just be me, but I notice that RPN and the stack work in a similar matter to that of the "stack" in Magic the Gathering, and in that sense, not overly complicated to understand. Makes me curious of if it could've influenced MTG, and whether or not some people could see using it as a way of practicing the use of the notation and the CPU stack.
Oh, definitely. The first time I played Magic, my friend was teaching me and he's like, "there's a stack. It's...a stack." Luckily we're both computer scientists, so I understood right away. It's very useful :)
The best part about having a RPN calculator is it will only be borrowed by anyone once and you will always get it back.
As a Pole, I'm incredibly impressed by his pronunciation of Łukasiewicz's name.
Perfect spelling of the Polish name, respect for digging it up.
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.
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. :)
This guy is a phenomenal teacher.
I've always thought the Reverse Polish sounded like a Chess Opening. Which makes it even better.
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.
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.
Brailsford's videos just get better and better. It's like a story unfolding.
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.
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
Please don't stop filming this wonderful man, and I won't stop watching :]
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.
One of the most important videos for any Computer Scientist. The stack is a fundamental data structure.
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!
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 😊
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
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.
You just gave me new confidence to take on Compilers courses. Thank you.
It's wonderful to see someone as passionate as this gentleman about his professional field
Its like the euler's identity of computer science. Somehow seemingly unrelated conclusions come together in a beautiful way.
I love listening to this guy talk about literally everything.
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,
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 :)
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.
Probably the most interesting video on the channel. Professor Brailsford is very interesting
I love how passionate this gentleman is about his craft. Great video and quite easy to understand! Thanks Computerphile.
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.
Too bad I did not find this channel when I was supposed to be studying all this.
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.
I'm gonna pop some stacks, only got operands in my pocket.
Brilliant explanation, love this guy.
I love how you are able simplify really complicated topics. Computerphile... thank you.
Best explanation of RPN and stack I’ve heard yet. 😊
I'm a time traveler from 4 years into the future and this is still the best explanation of the subject matter
These videos, like the ones about sorting algorithms and huffman trees are my favourite by far on this channel. Keep it up!
Splendidly explained! My year-long question on how computer determines which operation to be done first has FINALLY been solved.
I think this is Professor Brailsford's best Numberphile video yet!
These videos are so informative. I never leave this channel without learning something new. Great initiative!
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!
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
This was what made reading RPN click for me. Great video.
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.
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.
I wish I had such good tutors when I was a student. I enjoy every single one of his videos.
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
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.
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.
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 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
Pretty good pronunciation on Łukasiewicz's name.
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).
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
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.
seth094978
Yeah, the borrowing thing is quite true :)
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.
This is great, I love this guy. I already had a passing understanding of these concepts, but I had no idea they were related.
I really appreciate you taking the time to make this video. It really encourages me and its super informative.
Professor Brailsford's pronunciation of "Jan Łukasiewicz" is nearly perfect :) Thank you for that!
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. 😆
This seems such a cooler notation than the standard one. Especially in computing it gets incredibly confusing with operands. Some have higher priority, some go right to left some left to right amd stuff...
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.
Oh man, that takes me back to the mid-80s with HP calculators that use RPN and my sophomore data structures class!
I learned about RPN by programming in FORTH on the Redpower computer from the Minecraft mod :)
these videos are brilliant
Great video. This is as good an explanation of RPN as I have ever seen. RPN is especially useful when dealing with computers because it lays out the information in the same way the machine has to use it. It is however not great for non machines like humans. We do not use the information the same way a machine does. We see the entire line at once and then evaluate it. It is why I prefer TI calculators over HP calculators. I prefer to let the machine evaluate then execute the line. That makes life simpler for me. I really do not care if it is simpler for the machine.
I would recommend an HP calculator for anyone going into Computer Science or Engineering because these two disciplines require such heavy use of computers and writing original code it is useful in thinking in these program steps to begin with.
Not trying to start an argument, pun intended, but RPN is more natural than you think. If when you were being taught arithmetic they taught you to arrange your numbers vertically, you were using RPN. The dawn of the digital calculator actually caused a lot of confusion. TI's follow the throwback that early calculators only had three registers since only one operand could be preformed at a time. HP's stack flow is an analog to the conventional vertical 'pen and paper' method.
Always learning things from Professor Brailsford.
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.
These videos are so, so good. Thank you guys for putting them together.
Best explanation of this I've ever seen.
Marvelous way of explaining. Thank you computerphile.
Very nicely explained and awesome demonstration, much appreciated.
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.
Great video, better than my lecturer by far
Yes. I would like to see more of this please. Very interesting.
I was impressed, it was very good pronaunciation of name Łukaszewicz. :)
The David Attenborough of computers
props to professor Brailsford! very good pronunciation of Łukasiewicz surname
Yes Mr professor, you pronounced "Łukasiewicz" surname well. Great video!
OMG, I requested this one and they actually made it real. THANK YOU SO MUCH! =D
I have a modern scientific calculator which only gets used for some of the more advanced calculations I need to do when I'm not at my computer. But it is so much faster and easier to deal with complicated equations using a RPN calculator, as you type the values in the same order you would if you were solving it yourself.
Now that you can get RPN calculator applications for cell phones, and not have to fork out a load of money, doing calculations couldn't be easier.
Good video! I like the computer science topics, like the trees and stacks and math.
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!
I would like to see more videos on stacks, assembly language and compilers from computerphile.
Amazing explaination and demonstration. Thank you so much for posting this video!
I will watch any video of Prof David Brailsford talking
Brilliant! So illuminating of processes once mysterious to me! Thanks for another great video!
Will be taking a course on assembly in a week or so, this was a nice introduction. :)
Fantastic! Can't wait to learn more about stacks!!
Literally studied this in computing last week.
I always like presenting prefix/infix/postfix via binary trees when teaching people how to translate them. for example if you build a binary tree of the equation "a+b*c", where operands are leaves and operators are nodes, you'd get a tree that looks like this.
( + )
/ \
( a ) ( * )
/ \
( b ) ( c )
Now take your finger and start directly above the root of this tree. Draw an outline counter-clockwise around the tree hugging all the leaves and nodes. if you want to write this tree in prefix simply write down the node/leaf whenever your finger passes directly to the left of it. For infix is when you passes directly below one. And for postfix is when you pass directly to the right of one. In the end you would get these results
prefix: +a*bc
infix: a+b*c
postfix: abc*+
Pedagogical genius. Love going back to basics.
does this mean there is is going to be a video about the difference between the heap and the stack
Just as the tree mentioned in this video, a stack is an abstract data type. A heap, however, isn't. Just because the stack known from memory management is known as _the_ _stack_ in that context doesn't make it special as far as stacks go.
The more likely next step from here is the queue, since a stack is also called LIFO (last in, first out) and a queue is called FIFO (first in, first out).
So you're talking about a totally different branch of computer science called computer engineering. That doesn't mean that this won't be covered some day but they are currently just laying the groundwork for this with stuff that's essential in _all_ areas of computer science.
Penny Lane Heaps are data structures.
Penny Lane Science != Engineering. Science is research-oriented, engineering is the application of science to solve problems within some economic scope. Engineering, thus, cannot be a branch of science.
Also, "the stack" is extraordinarily special; as a data structure, it's LIFO, but it's singularly important because without it, contemporary, register-based CPUs cannot perform subroutine calls recursively. Whether implemented in hardware (as on x86) or in software (as on PowerPC and most other RISCs), "the stack" is absolutely vital for ... everything.
"The heap", however, is not "a heap" (usually), and so you're right to say it's not an abstract data type. However, it, nonetheless, remains vitally important, for it is the pool of memory from which stacks for processes and other data structures are typically allocated from.
I say typically because there is one language, Forth, which generally lacks a heap in this fashion. But, I digress.
Samuel Falvo II Consider quite a lot of computing research is funded by outside companies, many research projects are actually elaborating on new applications of computing. Same goes for non-academic companies like Google, which come up with new large-scale algorithms and can be considered science. I would say in field of computing, engineering and science are inseparable.
Samuel Falvo II Ok, replace "computer science" with "informatics" which is the name given to computer science in about any other language except English. If your argument still holds, then at least we aren't just arguing semantics.
I had hoped I made clear that I do not doubt that memory management is a worthy topic for videos to come but that this is totally besides the point. And the point is that Jordan Stocker apparently jumped to conclusions because he had heard "stack" in a very specialized context which probably kept him from seeing the bigger picture here and the fundamental importance of "stack" as an ADT and a concept. Now if you want to talk to me about that then please do, otherwise I'm afraid this discussion lacks the focus to keep me engaged.
Oskar Mamrzynski A heap, which has got nothing to do with _the_ heap as Samuel rightly said, is a data structure but _not_ an abstract data type. The abstract data type implemented using heaps is called "priority queue".
Wouldn't bc*a+ be more "stack efficient" than abc*+? Using the latter three items need to be pushed before the calculation begins, with the former there's only ever two items on the stack.
Some operators might not be commutative. (think about multiplying matrices)
I don't think efficiency was the point here. Using abc*+ demonstrates how you can have more than two operands on the stack and how they are evaluated. Had he used bc*a+, people might have gotten the wrong idea that there must always be at most two operands on the stack(since the second example also had two)
Lttlemoi But you don't directly multiply matrices on the stack, ultimately you have to break them down and perform the calculations on the components.
But you'd have to search for that event in the arguments you are entering, it's much easier to go from the start to the end with that kind of thing. It saves a lot of time. Imagine you have a very long 100+ arguments operation to do ...
Tom Furie That still doesn't mean that you can just swap the operands around. Matrices are only one example. If you are using lists and you want to concatenate them, the order of operands is obviously very important. (Lisp and Haskell come to mind, even though they use prefix instead of postfix)
The stack is only used for keeping your data around in a simple way. It's not used for the calculations themselves, which are completely irrelevant.
Additionally, you don't have to keep the variables themselves on the stack. You could also just use pointers, which allows you to mix objects from base classes and derived classes without any hassle with object size etc.
love you guys computerphile
*Finally, a place in computer science where size doesn't matter!*
I remember being very frustrated about writing in FORTH because it was a stack based language and the specific compiler I was using didn't allow you to make changes, you had to type everything right at ONCE! I tried 5 hours to make something that would have taken 30 minutes in LUA. ahh good days.
Really simple yet powerful and effective! great!
excellent teacher. soothing demeanor. in-depth knowledge helps a lot i guess!
This could just be me, but I notice that RPN and the stack work in a similar matter to that of the "stack" in Magic the Gathering, and in that sense, not overly complicated to understand. Makes me curious of if it could've influenced MTG, and whether or not some people could see using it as a way of practicing the use of the notation and the CPU stack.
Oh, definitely. The first time I played Magic, my friend was teaching me and he's like, "there's a stack. It's...a stack." Luckily we're both computer scientists, so I understood right away. It's very useful :)