Reverse Polish Grows on Trees - Computerphile

  Рет қаралды 94,041

Computerphile

Computerphile

Күн бұрын

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/nottscom...
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradycha...

Пікірлер: 139
@lordofduct
@lordofduct 10 жыл бұрын
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
@TheJaguar1983 6 жыл бұрын
Prof. Brailsford is my favourite Computerphile presenter.
@kyledaoust221
@kyledaoust221 10 жыл бұрын
I dont know dick about computers but I could listen to this guy talk all day
@xanokothe
@xanokothe 10 жыл бұрын
You are amazing Professor. You are the Morgan Freeman of Computerphile
@NickiRusin
@NickiRusin 10 жыл бұрын
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
@insect212 10 жыл бұрын
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.
@mattilindstrom
@mattilindstrom 10 жыл бұрын
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
@AureliusR 3 жыл бұрын
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
@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
@not_herobrine3752 10 ай бұрын
ive first found out that RPN exists after discovering forth, and found the idea of manipulating a stack of numbers quite interesting
@kevins8260
@kevins8260 9 жыл бұрын
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
@laughingvampire7555 2 ай бұрын
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.
@nihlovaccus9652
@nihlovaccus9652 10 жыл бұрын
Fantastic video. You've demonstrated the relationship between postfix notation, trees and stacks very elegantly.
@jdferreira
@jdferreira 10 жыл бұрын
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! :)
@TheAlexagius
@TheAlexagius 10 жыл бұрын
Explains it far better than my computer science teacher ever did....
@derejehailemariam677
@derejehailemariam677 5 жыл бұрын
A natural teacher. Rare and amazing teaching skill.
@gulllars4620
@gulllars4620 10 жыл бұрын
This professor is a joy listening to :)
@robl4836
@robl4836 10 жыл бұрын
A nice straightforward explanation. I'd just say that I find Polish already difficult, without reversing it ;)
@Tyranisaur
@Tyranisaur 10 жыл бұрын
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.
@ThePeaceableKingdom
@ThePeaceableKingdom 10 жыл бұрын
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... :)
@ButzPunk
@ButzPunk 10 жыл бұрын
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
@Robstafarian Жыл бұрын
LaTeX is wonderful.
@thoperSought
@thoperSought 10 жыл бұрын
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.
@eltyo340
@eltyo340 10 жыл бұрын
Brailsford videos are the best
@mikelipsey8837
@mikelipsey8837 10 жыл бұрын
Wish I had this gentleman when I took Comp. Sys. many years ago...
@Burak-pl1jl
@Burak-pl1jl 7 жыл бұрын
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
@cra0kalo
@cra0kalo 10 жыл бұрын
Great video looking forward to more by Professor Brailsford
@pascalcoole2725
@pascalcoole2725 4 жыл бұрын
Thanks David, although i still have to fiddle with it your talk helps me quiet a lot further.
@llewkcornosaj
@llewkcornosaj 10 жыл бұрын
You have an amazingly soothing voice. Pure butter
@xanokothe
@xanokothe 10 жыл бұрын
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?
@OneAndOnlyMe
@OneAndOnlyMe 3 жыл бұрын
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.
@tzkelley
@tzkelley 10 жыл бұрын
These videos remind me of how much I've forgotten.
@penfold-55
@penfold-55 10 жыл бұрын
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
@PeterWalkerHP16c
@PeterWalkerHP16c 9 жыл бұрын
...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
@herbertwyndham
@herbertwyndham 10 жыл бұрын
This is great! I remember coding a postfix calculator as an exercise in school
@Herdatec
@Herdatec 10 жыл бұрын
8:35 did I spend to much time on the internet when I immediately recognize the shape?
@iome87
@iome87 10 жыл бұрын
wow, this could help me a lot when i had to write a BASIC interpreter...
@FerroNeoBoron
@FerroNeoBoron 10 жыл бұрын
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
@ib9rt 10 жыл бұрын
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
@FerroNeoBoron 10 жыл бұрын
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.
@General1Cal
@General1Cal 10 жыл бұрын
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
@jannegrey 7 жыл бұрын
You learned polish when you were 14?? Congrats, it's a difficult language! :D
@Playncooler
@Playncooler 7 жыл бұрын
Professor, can you explain the Shunting Yard algorithm?
@jacklewis6392
@jacklewis6392 10 жыл бұрын
I wrote a browser based RPN calculator in CoffeeScript (with jquery). It's a lot of fun.
@divanvanzyl7545
@divanvanzyl7545 10 жыл бұрын
Professor Brailsford is awesome
@ImKingLouie
@ImKingLouie 10 жыл бұрын
I like this. More algorithms and data structures and less sensationalism.
@SigmundSkjelnes
@SigmundSkjelnes 10 жыл бұрын
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.
@rdubb77
@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.
@amydebuitleir
@amydebuitleir 10 жыл бұрын
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.
@pev_
@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!
@Andrei5656
@Andrei5656 10 жыл бұрын
Such a great professor. Thank you.
@yeticusrex1661
@yeticusrex1661 10 жыл бұрын
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.
@karlkastor
@karlkastor 10 жыл бұрын
Very interesting video! Maybe I'll try programming a calculator like this using recursions like the tree he's drawn.
@deandrereichelle831
@deandrereichelle831 2 жыл бұрын
Funny how this idea of the computer outsourcing the work to the human is alive and well today, in the form of Captcha
@macvii2113
@macvii2113 8 жыл бұрын
Good Job Professor. Respect !!!
@JoffreyB
@JoffreyB 6 жыл бұрын
video starts at 4:47
@MaxElkin
@MaxElkin 10 жыл бұрын
8:35 ahhh...
@PINGPONGROCKSBRAH
@PINGPONGROCKSBRAH 10 жыл бұрын
I'm sorry professor, but I'm way too hungover this morning to comprehend this lecture.
@AwesomeCrackDealer
@AwesomeCrackDealer 10 жыл бұрын
This guy loves himself some Reverse Polish and STACKSSSSSSSS
@edgeeffect
@edgeeffect 8 жыл бұрын
I got into programming in FORTH just to do my mates heads in with RPN ;)
@ConstantlyDamaged
@ConstantlyDamaged 10 жыл бұрын
Discussing RPN in computing and not talking about FORTH? you "Please follow up with more, I love RPN" !
@harrisonharris6988
@harrisonharris6988 9 жыл бұрын
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
@EvgenyPakhomov 8 жыл бұрын
+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
@blazerboy55 8 жыл бұрын
+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.
@Merlin5007
@Merlin5007 10 жыл бұрын
First to comment. Now i better watch it! Love this channel.
@KarnKaul
@KarnKaul 10 жыл бұрын
Mindblowing
@SigurdKristvik
@SigurdKristvik 10 жыл бұрын
Genius, I should learn to do this in the C programming language
@ThePhatHalo
@ThePhatHalo 5 жыл бұрын
I can't wait to try out the reverse polish with my gf!
@michelfug
@michelfug 10 жыл бұрын
Thx. Nice video. At 6:31 I spotted a little mistake in de diagram: the a and b operands are mislabeled.
@fabien2430
@fabien2430 10 жыл бұрын
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.
@MagnusTheUltramarine
@MagnusTheUltramarine 3 жыл бұрын
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
@megamef
@megamef 10 жыл бұрын
This guy is great
@talideon
@talideon 10 жыл бұрын
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.
@seanodonnell2228
@seanodonnell2228 8 жыл бұрын
Thanks.
@NNOTM
@NNOTM 10 жыл бұрын
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
@0pyrophosphate0 10 жыл бұрын
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
@mcvoid1 10 жыл бұрын
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
@NNOTM 10 жыл бұрын
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
@mcvoid1 10 жыл бұрын
NNOTM Yes, and yes. I didn't see you had more to say, and I confuse my left and right.
@TheElectromatter
@TheElectromatter 10 жыл бұрын
NNOTM rewrite your algorithm as an iterative function and you will see that it is equivalent to walking around the tree.
@jwilliams8210
@jwilliams8210 7 жыл бұрын
Fascinating!
@MagnusTheUltramarine
@MagnusTheUltramarine 3 жыл бұрын
do modern computers (CPU's, calculators, etc) still use this way of computing arithmetic when code is compiled to machine code?
@yousorooo
@yousorooo 10 жыл бұрын
So what's the algorithm for "walking counterclockwise"?
@JohnDobyns
@JohnDobyns 10 жыл бұрын
Where do you guys get line printer paper? I haven't seen it in decades ;)
@MegaMinerd
@MegaMinerd 7 жыл бұрын
In the illustration starting at 7:28, you wouldn't see any of the operators prematurely if you were looking the other way.
@DreadKyller
@DreadKyller 6 жыл бұрын
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.
@Rizhiy13
@Rizhiy13 10 жыл бұрын
Second tree is incorrect on the slideshow, c should be changed to a.
@Computerphile
@Computerphile 10 жыл бұрын
Many thanks for spotting this, I will add an annotation - and apologies! >Sean
@ReinaldoRauch
@ReinaldoRauch 10 жыл бұрын
Amazing vid! Keep this quality o/
@kolrabi
@kolrabi 10 жыл бұрын
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
@BGBTech 10 жыл бұрын
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
@kolrabi 10 жыл бұрын
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
@BGBTech 10 жыл бұрын
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, ...).
@sanjaybhatikar
@sanjaybhatikar 4 жыл бұрын
So what do loops (like for loop or while loop) look like on the stack and can RPN describe loops?
@wkiernan
@wkiernan 7 жыл бұрын
"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!
@kingemocut
@kingemocut 10 жыл бұрын
so, it's like when we use prime number trees..?
@kristover100
@kristover100 10 жыл бұрын
8:26 is a bit rude.
@amigojapan
@amigojapan 8 жыл бұрын
ok, and how do you generate the tree from an expression? I think this is the missing link i am missing//
@blazerboy55
@blazerboy55 8 жыл бұрын
+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.
@arani5896
@arani5896 5 ай бұрын
the goat
@vortyx090
@vortyx090 8 жыл бұрын
thanks man!
@GtaRockt
@GtaRockt 8 жыл бұрын
title sounds like some random English on a t-shirt they sell in Japan
@mahdiarnaufal567
@mahdiarnaufal567 8 жыл бұрын
you mean china
@billl605
@billl605 6 жыл бұрын
You don't want a reverse polish notation stain on your shirt.
@CCcrafted
@CCcrafted 10 жыл бұрын
Lol, 300th viewer. The next person won't know for sure what viewer they are
@mcvoid1
@mcvoid1 10 жыл бұрын
Hell yeah more CS.
@culwin
@culwin 10 жыл бұрын
He is the Lorax he speaks for the trees
@AlexSimpsonsPage
@AlexSimpsonsPage 10 жыл бұрын
Oops, the tree at 6:30 is wrong (has variables b, c, c instead of a, b, c)
@rjday753
@rjday753 10 жыл бұрын
Animation dude he said 'looking to the left'
@DGCDWJ
@DGCDWJ 10 жыл бұрын
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
@timotree3 7 жыл бұрын
DGCDWJ the professor meant looking to 90 degrees anticlockwise to the direction you're currently walking.
@haralampiev2000
@haralampiev2000 7 жыл бұрын
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
@DreadKyller 6 жыл бұрын
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
@billl605 6 жыл бұрын
ahhh ty so much @@timotree3
@Markus9705
@Markus9705 10 жыл бұрын
I loive this guy. :)
@piwi2005
@piwi2005 3 жыл бұрын
Not really true. Nobody was doing abc*+ on the HP48s. Actually everybody was doing bc*a+.
@martixy2
@martixy2 8 жыл бұрын
Power is right-associative though.
@ais4185
@ais4185 5 жыл бұрын
1:54 Ha! He didn't say "film"!
@RobertKelleyPhD
@RobertKelleyPhD 10 жыл бұрын
...when computer science is taught by "tree-huggers"...
@Calvinatorzcraft
@Calvinatorzcraft 7 жыл бұрын
RECURSIVE ARITHMETIC TIME
@tatopolosp
@tatopolosp 10 жыл бұрын
is it just a stretch.. anyway, thanks
@DeviousMalcontent2
@DeviousMalcontent2 10 жыл бұрын
I was about to say magic :D
@MaxElkin
@MaxElkin 10 жыл бұрын
First!
@noswonky
@noswonky 10 жыл бұрын
Tree hugger.
@yankeenobonagu6411
@yankeenobonagu6411 3 жыл бұрын
not not is is not not not is not
@willhi5
@willhi5 2 жыл бұрын
YOUR left, not THE left. Hope this helps someone
@veggiet2009
@veggiet2009 10 жыл бұрын
"'Look to your left' I think its some kind of political statement "
Reverse Polish Notation and The Stack - Computerphile
13:32
Computerphile
Рет қаралды 308 М.
The Font Magicians - Computerphile
19:31
Computerphile
Рет қаралды 367 М.
Can You Find Hulk's True Love? Real vs Fake Girlfriend Challenge | Roblox 3D
00:24
كم بصير عمركم عام ٢٠٢٥😍 #shorts #hasanandnour
00:27
hasan and nour shorts
Рет қаралды 11 МЛН
FOREVER BUNNY
00:14
Natan por Aí
Рет қаралды 31 МЛН
Turing's Enigma Problem (Part 1) - Computerphile
19:00
Computerphile
Рет қаралды 1,3 МЛН
The Great 202 Jailbreak - Computerphile
19:55
Computerphile
Рет қаралды 519 М.
A world from a sheet of paper - Tadashi Tokieda
1:01:13
Oxford Mathematics
Рет қаралды 388 М.
How Huffman Trees Work - Computerphile
11:07
Computerphile
Рет қаралды 253 М.
The Strange Physics Principle That Shapes Reality
32:44
Veritasium
Рет қаралды 6 МЛН
DIY Programming Language #1: The Shunting Yard Algorithm
37:10
Fibonacci Programming - Computerphile
8:57
Computerphile
Рет қаралды 245 М.
Cracking Enigma in 2021 - Computerphile
21:20
Computerphile
Рет қаралды 2,5 МЛН