Reverse Polish Grows on Trees - Computerphile

[@lordofduct]

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.

[@TheJaguar1983]

Prof. Brailsford is my favourite Computerphile presenter.

[@xanokothe]

You are amazing Professor. You are the Morgan Freeman of Computerphile

[@kyledaoust221]

I dont know dick about computers but I could listen to this guy talk all day

[@mattilindstrom]

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.

[@AureliusR]

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.

[@christopherpepin6059]

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.

[@not_herobrine3752]

ive first found out that RPN exists after discovering forth, and found the idea of manipulating a stack of numbers quite interesting

[@NickiRusin]

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.

[@insect212]

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.

[@kevins8260]

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!

[@laughingvampire7555]

As a user of 48G calculator, I love it, is just one of the best ways to code and use, if you are doing calculation of complicated equations you can start in any order you want and adjust to it as your read the equation, but with standard infix notation it has to follow the order of operations and the parenthesis and there is no room for a mistake or you will have to start again. in the RPN calculator you can use the infix notation, in the HP48 it was called algebraic, and it had a nice visual editor to enter everything but it was a mess, I always preferred RPN. With algebraic you could fix input errors but the whole expression couldn't fit in the small screen.

[@gulllars4620]

This professor is a joy listening to :)

[@nihlovaccus9652]

Fantastic video. You've demonstrated the relationship between postfix notation, trees and stacks very elegantly.

[@ThePeaceableKingdom]

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

[@jdferreira]

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

[@derejehailemariam677]

A natural teacher. Rare and amazing teaching skill.

[@TheAlexagius]

Explains it far better than my computer science teacher ever did....

[@thoperSought]

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.

[@robl4836]

A nice straightforward explanation. I'd just say that I find Polish already difficult, without reversing it ;)

[@xanokothe]

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?

[@ButzPunk]

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.

[@Robstafarian]

LaTeX is wonderful.

[@mikelipsey8837]

Wish I had this gentleman when I took Comp. Sys. many years ago...

[@eltyo340]

Brailsford videos are the best

[@pascalcoole2725]

Thanks David, although i still have to fiddle with it your talk helps me quiet a lot further.

[@llewkcornosaj]

You have an amazingly soothing voice. Pure butter

[@Tyranisaur]

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.

[@penfold-55]

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

[@herbertwyndham]

This is great! I remember coding a postfix calculator as an exercise in school

[@FerroNeoBoron]

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.

[@ib9rt]

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

[@FerroNeoBoron]

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.

[@cra0kalo]

Great video looking forward to more by Professor Brailsford

[@OneAndOnlyMe]

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.

[@Burak-pl1jl]

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

[@Playncooler]

Professor, can you explain the Shunting Yard algorithm?

[@yeticusrex1661]

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.

[@General1Cal]

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.

[@jannegrey]

You learned polish when you were 14?? Congrats, it's a difficult language! :D

[@divanvanzyl7545]

Professor Brailsford is awesome

[@iome87]

wow, this could help me a lot when i had to write a BASIC interpreter...

[@tzkelley]

These videos remind me of how much I've forgotten.

[@PeterWalkerHP16c]

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

[@jacklewis6392]

I wrote a browser based RPN calculator in CoffeeScript (with jquery). It's a lot of fun.

[@ImKingLouie]

I like this. More algorithms and data structures and less sensationalism.

[@amydebuitleir]

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.

[@michelfug]

Thx. Nice video. At 6:31 I spotted a little mistake in de diagram: the a and b operands are mislabeled.

[@Andrei5656]

Such a great professor. Thank you.

[@karlkastor]

Very interesting video! Maybe I'll try programming a calculator like this using recursions like the tree he's drawn.

[@harrisonharris6988]

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.

[@EvgenyPakhomov]

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

[@blazerboy55]

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

[@rdubb77]

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.

[@MaxElkin]

8:35 ahhh...

[@macvii2113]

Good Job Professor. Respect !!!

[@megamef]

This guy is great

[@edgeeffect]

I got into programming in FORTH just to do my mates heads in with RPN ;)

[@KarnKaul]

Mindblowing

[@SigurdKristvik]

Genius, I should learn to do this in the C programming language

[@seanodonnell2228]

Thanks.

[@jwilliams8210]

Fascinating!

[@JohnDobyns]

Where do you guys get line printer paper? I haven't seen it in decades ;)

[@Herdatec]

8:35 did I spend to much time on the internet when I immediately recognize the shape?

[@SigmundSkjelnes]

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.

[@deandrereichelle831]

Funny how this idea of the computer outsourcing the work to the human is alive and well today, in the form of Captcha

[@MagnusTheUltramarine]

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

[@PINGPONGROCKSBRAH]

I'm sorry professor, but I'm way too hungover this morning to comprehend this lecture.

[@AwesomeCrackDealer]

This guy loves himself some Reverse Polish and STACKSSSSSSSS

[@fabien2430]

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.

[@ThePhatHalo]

I can't wait to try out the reverse polish with my gf!

[@yousorooo]

So what's the algorithm for "walking counterclockwise"?

[@ConstantlyDamaged]

Discussing RPN in computing and not talking about FORTH? you "Please follow up with more, I love RPN" !

[@pev_]

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!

[@MegaMinerd]

In the illustration starting at 7:28, you wouldn't see any of the operators prematurely if you were looking the other way.

[@DreadKyller]

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.

[@mcvoid1]

Hell yeah more CS.

[@MagnusTheUltramarine]

do modern computers (CPU's, calculators, etc) still use this way of computing arithmetic when code is compiled to machine code?

[@kolrabi]

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.

[@BGBTech]

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.

[@kolrabi]

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.

[@BGBTech]

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

[@vortyx090]

thanks man!

[@sanjaybhatikar]

So what do loops (like for loop or while loop) look like on the stack and can RPN describe loops?

[@arani5896]

the goat

[@wkiernan]

"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!

[@talideon]

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.

[@ReinaldoRauch]

Amazing vid! Keep this quality o/

[@JoffreyB]

video starts at 4:47

[@NNOTM]

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

[@0pyrophosphate0]

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.

[@mcvoid1]

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)

[@NNOTM]

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?

[@mcvoid1]

NNOTM Yes, and yes. I didn't see you had more to say, and I confuse my left and right.

[@TheElectromatter]

NNOTM rewrite your algorithm as an iterative function and you will see that it is equivalent to walking around the tree.

[@Rizhiy13]

Second tree is incorrect on the slideshow, c should be changed to a.

[@Computerphile]

Many thanks for spotting this, I will add an annotation - and apologies! >Sean

[@kingemocut]

so, it's like when we use prime number trees..?

[@rjday753]

Animation dude he said 'looking to the left'

[@DGCDWJ]

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.

[@timotree3]

DGCDWJ the professor meant looking to 90 degrees anticlockwise to the direction you're currently walking.

[@haralampiev2000]

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!

[@DreadKyller]

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.

[@billl605]

ahhh ty so much @@timotree3

[@CCcrafted]

Lol, 300th viewer. The next person won't know for sure what viewer they are

[@GtaRockt]

title sounds like some random English on a t-shirt they sell in Japan

[@mahdiarnaufal567]

you mean china

[@billl605]

You don't want a reverse polish notation stain on your shirt.

[@kristover100]

8:26 is a bit rude.

[@Merlin5007]

First to comment. Now i better watch it! Love this channel.

[@culwin]

He is the Lorax he speaks for the trees

[@amigojapan]

ok, and how do you generate the tree from an expression? I think this is the missing link i am missing//

[@blazerboy55]

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

[@Markus9705]

I loive this guy. :)

[@AlexSimpsonsPage]

Oops, the tree at 6:30 is wrong (has variables b, c, c instead of a, b, c)

[@ais4185]

1:54 Ha! He didn't say "film"!

[@martixy2]

Power is right-associative though.

[@Calvinatorzcraft]

RECURSIVE ARITHMETIC TIME

[@DeviousMalcontent2]

I was about to say magic :D

[@piwi2005]

Not really true. Nobody was doing abc*+ on the HP48s. Actually everybody was doing bc*a+.

[@RobertKelleyPhD]

...when computer science is taught by "tree-huggers"...

[@noswonky]

Tree hugger.

[@tatopolosp]

is it just a stretch.. anyway, thanks

[@willhi5]

YOUR left, not THE left. Hope this helps someone

[@yankeenobonagu6411]

not not is is not not not is not

[@MaxElkin]

First!

[@veggiet2009]

"'Look to your left' I think its some kind of political statement "