Reverse Polish Grows on Trees - Computerphile
ฝัง
- เผยแพร่เมื่อ 27 พ.ค. 2014
- Why use Reverse Polish Notation? How does it relate to trees in Computer Science? Professor Brailsford explains how RPN arises naturally, as a linearized form of a tree.
For further research, the Prof suggests you seek out material on the topics of "Postorder Tree Traversal" and "Dijkstra's Shunting Yard"
Correction: In the graphic at 06:30, on the illustration of the second tree, the A is incorrectly labelled as a C.
Reverse Polish Notation & the Stack: • Reverse Polish Notatio...
The Dawn of Desktop Publishing: • The Dawn of Desktop Pu...
Upside Down Trees: • How Huffman Trees Work...
Domino Addition - Numberphile: • Domino Addition - Numb...
/ 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
I dont know dick about computers but I could listen to this guy talk all day
You are amazing Professor. You are the Morgan Freeman of Computerphile
In some sense RPN "is a way of making you do all the hard work". In another, it is a way of taking out the hard work of converting one's thought proceses into the infix convention.
My first real experience with RPN came with my first university year and the HP-28C (I had had some passing encounters with the HP-41C and the 10C). To my surprise, instead of being a chore, the RPN method was for me a perfectly natural way of expressing my intent in a calculation. Many of my (also physicist) friends tell the same story: for a slightly scatter-brained way of numerical entry, they would not trade RPN for anything.
Feel free to drop something botched. Just SWAP or 1/x (after the fact) an incorrect division entry order. Transform the stack as you please. Chunk the equation into digestible bits.
RPN is perfect for my way of thinking in numerical calculations, but as always, tastes do differ.
However, even the HP folks admitted that algebraic entry (as TI was doing) was much easier and simpler. Hence why RPN fell out of use. It actually does take more up-front training. You end up using your tool in a way which contradicts how all written math is done. I like the concept of RPN and I like HP calcs, but it's important to recognize that it's *not* inherently superior. It forces you to re-arrange the equation in your head, instead of just typing it in as you would write it down.
I feel like one thing that is being undersold is that infix calculators, in an attempt to take away the hard work, seriously end up gimping the user by robbing them access to the stack. Meanwhile postfix and prefix calculators are pretty much forced to give you access to a stack and it greatly expands the capabilities of the calculator.
A great example being looking at the quadratic formula, which is often one of the first programs people are taught to put in their calculators. When you solve it you don't just get one solution, you usually get two. A RPN calculator handles that perfectly. It just pushes both values to the stack. Both values become readily available for you or your programs to use in an incredibly predictable manor.
Meanwhile an infix calculator isn't really set up to store temporary values. The best most of them will do is store one of the solutions in an ANS variable. If you want both answers though you are just out of luck without resorting to global variables. So on infix calculators you are stuck writing programs that have to stand pretty much completly alone. Creating actual functions that can feed each other was only supported on the most expensive of the TI calculators. Even then the functionality of those functions was limited as you couldn't return complex data structures, something trivial to do on an RPN calculator.
ive first found out that RPN exists after discovering forth, and found the idea of manipulating a stack of numbers quite interesting
I remember the first time I wrote my own mathematical script interpreter. Parsing strings into trees and traversing them into what was basically postfix to be operated in a simulated stack was the approach I took. I thought myself quite the genius for inventing such an awesome way of approaching the problem!
Not but a few hours later... my ego popped.
I will say though, it's moments like those that make me enjoy math and computer science. Even the first time you're explained it, and how elegant many processes are, I find it beautiful. It's why I continue on in this career.
This professor is a joy listening to :)
The animation at 7:00 confused me for just a moment, because the professor said "keep looking to my left" but the animated man keeps looking straight ahead facing 1st the right and then the left (from our point of view).
I then realized we're looking at the tree from above and the man from the side. If we were seeing the man from above as well, he would always be looking at the tree on his left while moving forward as he circumferences it counter clockwise.
I also realized that would be a lot harder to draw... :)
Prof. Brailsford is my favourite Computerphile presenter.
Fantastic video. You've demonstrated the relationship between postfix notation, trees and stacks very elegantly.
You sir, are very engaging. I love the way you explain everything. I'm a junior CS student at an Oregon University and I'd listen to your lectures any day over my current professors!
I really like this professor. He is so passionate about his ideas and has a very happy mood when explaining stuff! He reminds me of my grandfather, a really smart guy who loved to teach me things! Even though I already knew everything he taught us so far, I really enjoy seeing these videos, and I get thrilled when a new Computerphile video is with Prof. Brailsford! :)
Explains it far better than my computer science teacher ever did....
This is fanatic. I was trying to learn about this and failing, but then I decided to go on computerphile for fun and it explained it perfectly.
A couple days ago I finished a project that involved parsing a string with a function in it to then get the function value for a whole bunch of x values. Literally did what's described in this video - converted it into reverse polish, then created a binary tree with all the operations. Works like a dream.
0:46 I've never thought of RPN as hard, or something that needs converting to. infix calculators always put a much higher burden on my memory. with RPN, the only thing that gets me *sometimes,* when I haven't been using it for a while, is what's being divided into what.
I feel like, when I look at the stack on an rpn calculator-and maybe this is the key: I never had one that didn't display at least some of the stack-I know what's going to happen next. but, with infix calculators, I was never sure if I hit '+' already, or what the last number I put in was, etc.
8:35 ahhh...
A natural teacher. Rare and amazing teaching skill.
Great video looking forward to more by Professor Brailsford
Brailsford videos are the best
You have an amazingly soothing voice. Pure butter
there is a problem with the 27/9/3 issue....
27/9/3 as said in the video has two answers however what is really being asked is:
27/1 * 1/9 * 1/3
multiply the top's and bottoms you get 27 * 1 * 1 = 27
1 * 3 * 9 = 27
therefore 27/27 = 1
so to get around that issue, just use the inverse operator
Such a great professor. Thank you.
Wish I had this gentleman when I took Comp. Sys. many years ago...
A nice straightforward explanation. I'd just say that I find Polish already difficult, without reversing it ;)
Thanks David, although i still have to fiddle with it your talk helps me quiet a lot further.
This is great! I remember coding a postfix calculator as an exercise in school
Good Job Professor. Respect !!!
I thought reverse Polish notation was just something interesting which I'd never really use, but it turns out, it came in real handy because I've been writing in LaTeX and had to make some modifications to my style .bst to format my references the way the uni likes them. Thanks to your earlier lessons on it, I was able to understand how to write the little bits of code I needed and now I'm kinda in love with it... such a beautiful, logical way to write code.
LaTeX is wonderful.
The Postscript is really simple. As Professor said "The machine let you do all the hard work" which is "assembly" the Postscript or the tree. Will have a video about the algorithm for it?
Before this video, I was wondering how I would remember all this stuff, but after seeing your cheat everything has changed. Thank you a lot sir! Best cheat ever seen. Haha
How to traverse the tree: draw a line (mentally) around the tree and to get the different orders, do this:
Postfix(RPN): write the thing when you are to the right of it.
Infix: write ( when you are to the left of a thing, write the thing when you are under it and write ) when you are to the right of it.
Prefix: write the thing when you are to the left of it.
Fascinating!
Professor, can you explain the Shunting Yard algorithm?
Professor Brailsford is awesome
Amazing vid! Keep this quality o/
These videos remind me of how much I've forgotten.
...added to my list of great lecturers. (In no particular order)
David Attenborough
Dr Jim Al Khalili
Dr Iain Stewart
Dr Aubrey Manning
David Malone
Dr Michael Mosley
Dr Alice Roberts
Dr Brian Cox
Dr David Brailsford
Very interesting video! Maybe I'll try programming a calculator like this using recursions like the tree he's drawn.
Mindblowing
wow, this could help me a lot when i had to write a BASIC interpreter...
I always used to be amazed that the low processing power of the original HP LaserJet was able to parse and interpret something as high level as PostScript. Makes sense now.
He’s doing a Postorder Depth First traversal of the tree, you’re segregating the operands from the operators by doing the leaf nodes their root nodes.
Excellent video....my only complaint is that they didn't show the HP15C....which really is not a complaint....just a personal nitpick....still have my 15C that I use almost daily for the last 32 years.
While a good explanation of RPN per se, I think the video made *using* an RPN calculator sound harder than it actually is. My way of thinking about it is that you do the calculation in the same order you would do it with a pencil and paper. Figure out the next operation you need to do, make sure the operands are on the stack, and do the operation. So to calculate a+b*c, I would enter bc*a+, not abc*+. The result is the same, but I don't have to worry about stack overflow because I never have more operands on the stack than I need for the next operation.
This guy is great
Thx. Nice video. At 6:31 I spotted a little mistake in de diagram: the a and b operands are mislabeled.
So what do loops (like for loop or while loop) look like on the stack and can RPN describe loops?
8:35 did I spend to much time on the internet when I immediately recognize the shape?
I'm sorry professor, but I'm way too hungover this morning to comprehend this lecture.
Where do you guys get line printer paper? I haven't seen it in decades ;)
If you have an old infix calculator you might be able to try this.Tell your calculator to calculate 2^3^4. I had an infix calculator that assumed that all operators were left-associated and it gave me 8^4=4096. But on a newer calculator it gave me the correct right-associative answer of 2^81=~2*10^24. It might be contrived but it's an interesting error.
But I want 2^3^4 to be treated as (2^3)^4 and give me 4096, because that is the most common scenario by far when doing computations. For instance I would rather hope that e^(ln 10)^3 gives me 1000 and not 200400.18. If I had a calculator that gave the latter answer I might be inclined to reprogram it with a hammer...
ib9rt
Actually, you probably don't. If you read a typeset paper on mathematics and it has a 2 with a small 3 above it to the right and an even smaller 4 above that and to the right (or some other operand) it translates to a right-associative operation when written out without typesetting since (2^3)^4 = 2^(3*4). It's also a natural extention into tetration since it doesn't require parentheses.
I'll admit that it's rather contrived and likely to screw up anyone not in the know which is why I nerd sniped some of my friends with it. I imagine almost all new calculators will probably use the right-associative version from now on though.
I always wonder if the reason languages like C and Java don't have an operator for exponentiation on integral types is because of this. I find the potential that there's someone out there who implements a library that overloads the bitwise xor operator as exponentiation and a poor sap that uses that operator twice in a row without understanding the associativity of the operators in the mathematical paper they probably got the algorithm from and the ones in the language to be pretty funny.
I wrote a browser based RPN calculator in CoffeeScript (with jquery). It's a lot of fun.
You know I wondered and pondered this idea since I learned the trick in c++ for 14 years! it was so simple, so int =+1, I always knew it was reverse something just did not know why. so I would explicitly code it so I would not forget, such int a int b, int c=b+a.
You learned polish when you were 14?? Congrats, it's a difficult language! :D
thanks man!
Most calculators got lost when people loan it, and forget to return it. Rpn calculators have the great advantage that most people can't use it there and then, and leave it.
I like this. More algorithms and data structures and less sensationalism.
Thanks.
First to comment. Now i better watch it! Love this channel.
So what's the algorithm for "walking counterclockwise"?
Funny how this idea of the computer outsourcing the work to the human is alive and well today, in the form of Captcha
do modern computers (CPU's, calculators, etc) still use this way of computing arithmetic when code is compiled to machine code?
I think there is a mistake or something that should be cleared (at 6:31):
(a+b)*c in reverse polish is: cab+x, and following the tree shape, it should be something like this:
.......+
..X b
c a
Hi, anticlockwise method ok for computer, RPN users probably never use it, indeed it's much easier to type b c * a + instead of a b c * +.
You start with inner operations (b*c) and then add a, it's nothing more than what human do when they don't have calculator.
how does the compiler handle multiply divides in that case?
If you gave it (in RPN): a b c / /
You would want it to do left-associative division and so you'd want it to do a/b then divide that result by c, but if you think about how it would work with the stack b and c would be at the top and so it would not be able to access the a underneath.
One way of possibly doing it would be as follows:
change the notation to be: a b 1 c / / / (put a 1 before the last divider operand and add another division)
the divide as normal and add to the stack, for example:
27 9 1 3 / / / (stack: [])
fill in stack = [27,9,1,3] (leftmost on bottom)
first divide, divide 2nd to top by top
so divide 1/3 = 1/3rd
stack = [27, 9, 1/3]
second divide, divide 2nd to top by top
so divide 9/0.33333... = 27
stack = [27,27]
third divide, divide 2nd to top by top
so divide 27/27 = 1
stack = [1]
equation solved correctly.
+Harrison Harris
For "(a / b) / c" you could just write in RPN "a b / c /"
RPN doesn't mean that all of the operators must be at the end of an expression.
+Harrison Harris There are also stack manipulation operations such as SWAP and ROT (swap and rotate).
1 2 3 SWAP => 1 3 2
1 2 3 ROT => 2 3 1
So given "a b c" and trying to achieve "(a/b)/c" you can do "a b c ROT ROT / /" or just "a b / c/" like the other commenter said.
I got into programming in FORTH just to do my mates heads in with RPN ;)
Genius, I should learn to do this in the C programming language
Walking around an actual tree doesn't really intuitively correspond to an algorithm one would actually use in practice, though, does it?
I would just say
function reversePolish (tree)
if (isLeaf)
then
print operand
else
reversePolish (leftChild)
reversePolish (rightChild)
print operator
end
I think he definitely could have simplified that explanation. What he's doing is a depth-first search, which I think should have been mentioned. If you follow the path that he drew, it's much easier to say that you write down anything you find while moving back toward the top of the tree. Or, anything immediately to the left of your path while you draw it can be written down. There's no need to differentiate between the operators and operands.
Sure. Walking a tree is actually simpler, though harder to see the bigger picture because it's recursive. It looks like this:
visit(node):
if isOperand(node):
print(node)
else:
visit(node.right)
visit(node.left)
print(node)
0pyrophosphate0
Ah, yeah, that makes sense.
Sean Wolcott Shouldn't you print the left node first and then the right node? Also, isn't that exactly what I wrote?
NNOTM Yes, and yes. I didn't see you had more to say, and I confuse my left and right.
NNOTM rewrite your algorithm as an iterative function and you will see that it is equivalent to walking around the tree.
so, it's like when we use prime number trees..?
the goat
I can't wait to try out the reverse polish with my gf!
I loive this guy. :)
Oops, the tree at 6:30 is wrong (has variables b, c, c instead of a, b, c)
Hell yeah more CS.
Animation dude he said 'looking to the left'
In the animation dude's defense, the professor was being confusing. He kept saying "looking to the left", but at the same time he kept talking about a node in the tree when he passed by it, whether the node was to the left or not. If he truly only ever looked to the left, he would never see an operator before an operand, and wouldn't have to ask the question "can you write it down?".
You can see that the professor messes up on the root node (the plus) when he asks if you can write it down when he's at the bottom of the node. From the bottom of the node while looking left, you can't see the node at all. So he shouldn't have mentioned it in the first place. When the root node finally is to the left of the walking dude, he will have passed all other nodes and the root will be the only one left to write down. So I can understand why the animation guy was confused.
DGCDWJ the professor meant looking to 90 degrees anticlockwise to the direction you're currently walking.
actually, the whole tree is turned 90 degrees to the left (or anticlockwise) in the professor`s paper - so he is absolutely right, but the animation is not so accurate!
Not to YOUR left, to the left from the perspective of the character walking around the tree, imagine you're the character, and you're walking forward around the tree, then you look to the left. Not to the left on the paper, the left direction is dependent on what direction the character is moving.
ahhh ty so much
@@timotree3
In the illustration starting at 7:28, you wouldn't see any of the operators prematurely if you were looking the other way.
yeah, but you would see B before A and thus you'd end up with bac*+ which is definitely not what you want. If you're looking to the right you'd also have to then specify a limit of how far to the right can you actually see. since the example is huggint the tree to the characters left side, you only see the immediate node next to you, while for this to work with the right side would require range, and would mess up even more on more sophisticated trees.
ok, and how do you generate the tree from an expression? I think this is the missing link i am missing//
+amigojapan Basically, you start at the deepest level of your expression and chain those bits together.
Consider the infix expression "(1+2)/(3+4)". You can see that before doing the division you need to do each addition, starting with the numerator, then divide those two results together (in the correct order, of course).
postfix( 1 2 + ) = infix( 1 + 2 )
postfix( 3 4 + ) = infix( 3 + 4 )
postfix( a b / ) = infix( a / b )
Chaining them together:
postfix( 1 2 + 3 4 + /) = infix( ( 1 + 2 )/( 3 + 4 ) )
Notice the number of parentheses used for each style. The RPN uses 0 parentheses, which means fewer keystrokes and faster input.
This guy loves himself some Reverse Polish and STACKSSSSSSSS
Discussing RPN in computing and not talking about FORTH?
you "Please follow up with more, I love RPN" !
Second tree is incorrect on the slideshow, c should be changed to a.
Many thanks for spotting this, I will add an annotation - and apologies! >Sean
8:26 is a bit rude.
Of course, if you have a syntax tree like that you don't really need the rpn to evaluate the expression anymore. Just recursivly evaluate each node.
that can be done, but a lot comes down to performance:
directly interpreting the syntax-tree tends to make for a fairly slow interpreter (say, 1000x slower than native C);
compiling to bytecode, it can be made a fair bit faster, more so if the bytecode already has all the type-information and variable locations worked out.
if you then directly interpret the bytecode, often it may be instead closer to 100x (most of the time typically going into a "while/switch" loop or similar construction).
otherwise, we can convert it to threaded-code (interpreting via a series of direct function calls), and get maybe 10x-30x of native speed;
if converted into naive ASM / machine-code, and then run, it may be around 3x-5x of native C;
throw a register allocator and an optimizer on it, and it may be 1x-2x.
so, typically, static compilers will convert everything to optimized machine code, so that it runs fast (albeit the compiler is slower and the code isn't really portable). compilers for VMs will often compile to a stack-based bytecode, leaving it up to the backend what to do with the code (say, directly interpreting single-use functions, and JIT compiling frequently-used functions, ...).
like, fast as computers are, for many things performance can still often be an issue.
some VMs will use a register-oriented bytecode (ex: like Dalvik or LLVM), which has pros and cons vs a stack bytecode: it is more complicated to produce by a compiler, but can be higher-performance for threaded-code or JIT output (for a still relatively simple backend, mostly due to typically needing 30-60% fewer operations to accomplish a task and being able to put more of the work on the compiler). (note: "registers" in this sense are closer to temporary-variables than to CPU registers).
also possible is to use a stack-based bytecode, but convert to a register IR internally for the threaded-code or JIT, allowing for simpler compilers at the cost of a more complicated backend (they now need to flatten the stack onto registers/temporaries and similar, include a basic optimizer, ...). this being fairly common in stack-based VMs.
Yes, you're absolutely right about the performance aspect of course. I was assuming that the code is parsed and executed exactly once (like for example in some kind of calculator application), in which case recursive evaluation should be faster, I suspect. That is, however, unrealistic for most real programs out there.
Björn P.
yeah, could be.
this is a fairly common strategy in many LISP variants IIRC.
also fairly common though in these cases (such as in a shell or shell-script interpreter or similar) is to directly parse the code and execute commands on a token-by-token basis (without building an intermediate AST), where generally the input is a big glob of code.
likewise, in assemblers, it is fairly common to go fairly directly from the ASM to the machine-code output (with no intermediate AST).
in past experiments, I had observed that it was possible to feed about 10-15 MB/sec of ASM code through an assembler, which seemed "probably fast enough" at the time.
going directly from tokens to bytecode would probably be a bad idea for an HLL compiler though (would tangle/complicate things and hinder AST-level operations, such as expression folding, ...).
Er... RPN doesn't really have anything to do with trees. Infix does, but not RPN. RPN is a linearisation of a tree. For instance, you could linearise a tree representing a set of operations in infix using Dijkstra's shunting-yard algorithm. At best, this is kind of a complicated explanation of the shunting-yard algorithm.
"It makes you do all the hard work" No! At least, not unless you are trying to get the correct answer on a test where some villain has written out an equation without guiding parentheses - and what that would be is not a test to see if you can solve a particular numerical problem, but a test to see only whether you had memorized the arbitrary rules of priority.
If you are trying to solve an actual problem - e.g. converting Fahrenheit to Centigrade - you already know the desired order of the operations you want to perform - in that example, first subtract 32, then multiply by 5, then divide by 9. Three operations: subtract, multiply, divide, boom, done.
Now suppose you want to write out the equation in infix format. You have to subtract, multiply, divide, and on top of that you must then pore over the equation referring to a memorized look-up table ("PEMDAS") and analyzing where its arbitrary order of operations will screw up the answer, and then selectively insert parentheses, and hope you haven't made a mistake. Then if you pass this equation to a computer or calculator, it has to do all that work in reverse. So you work harder AND the computer works harder!
He is the Lorax he speaks for the trees
1:54 Ha! He didn't say "film"!
I know and understand all this, BUT I think there is a rather serious fault in this video and that is: how do you construct the tree in the first place! He just makes a tree from an expression but never explains how the tree was made, how did he decide to put operands and operators in those specific positions!
video starts at 4:47
Lol, 300th viewer. The next person won't know for sure what viewer they are
Power is right-associative though.
is it just a stretch.. anyway, thanks
title sounds like some random English on a t-shirt they sell in Japan
you mean china
You don't want a reverse polish notation stain on your shirt.
Not really true. Nobody was doing abc*+ on the HP48s. Actually everybody was doing bc*a+.
I was about to say magic :D
First!
...when computer science is taught by "tree-huggers"...
RECURSIVE ARITHMETIC TIME
not not is is not not not is not
Tree hugger.
Forth.
YOUR left, not THE left. Hope this helps someone
'❤ Forth?' if 'like comment' then