What we're going to look at today is to extend this story about stacks and reverse polish a little bit further
Many of you said oh, yeah, I
learned about postfix reverse polish when I had an HP calculator and in those
Comments, you've helped to answer some of the questions that other commenters have said well
Why would you ever use reverse polish it does your head in as the saying goes do people really have to think like that
Why do calculator manufacturers and why do the inventors of the PostScript language force it on us and the answer is very simple
it makes
Underpowered machinery a lot easier to work
Well, if the machinery makes you do all the hard work of converting infix
Which you're much more comfortable with into reverse polish and it doesn't have to do that job
That's why relatively low-powered
calculators could do so much and it's why looking back at my other video about
The desktop publishing revolution at the end of that. I tried to make clear that the PostScript interpreter was running on
Underpowered hardware and one of the reasons it could succeed in doing that is again, it makes you do all the hard work
I think it's interesting its own right and it's also interesting when you're trying to delve a little bit more
into
Compilers interpreters and computer science general principles because under the hood these kind of issues
About stacks and trees are utterly utterly
foundational in the whole of our subject today
I want to get in properly into trees and show you how fundamental they are
And an ideal way to do it is to pick up from the end of my stacks and reverse polish video
Which you might want to look at first if you haven't already
Pick up from where we left off and say what's the fundamental?
Story behind all of this and the answer is it's the tree shape
I started off by
writing down the arithmetic expression A plus B multiplied by sin if you accept
The multiplied must be done first then
the reverse polish notation
It would of course be a
B C Star Plus remember our PN
Reverse polish. You can call it postfix. Also if you want to
fair enough that somehow you've got to
know which of the high priority operators in which of the low priority operators in other words, which ones get done first and
Multiply and divide are of the same precedence as each other. They're high precedence. They get done first
But what happens if you've got a string of the stuff all of which involves exactly the same operator?
Do you do it left to right or right to left? Does it matter let's take a very very simple case
27 + 9 + the range should it be add?
nine to 27 first and then add three or should it be
keep the 27 and add it to what you get when you
Do the 9 + 3 addition first? This is called
left
Association this one of course is called right associativity or right?
Association and look with plus as ever. There's a very little problem so it doesn't matter at all. Ah
But here comes the one where it massively matters
How about 27 divided by 9?
divided by 3
Do you do that and then that all your group here?
Well, the default is always the left
Association you go left to right
Try this only calculator. If you find that that is exactly what it does
27 divided by 9 is 3 3 divided by 3
Actually gives us an integer answer here a 1 if you did it the other way of
27
divided by
9/3
The answer then would be nine
The ordering in which you do things is twofold
First of all, you do your high priority things first
and
then if you've got things of equal priority strung out in front of you you do them left to right it all comes down to
Trees back to the beginning a plus B times C
What?
Diagram could I draw that makes it happen correctly?
In other words makes the multiply be done first and the answer is draw a tree
draw yourself a tree
House ever it's computer scientists
We all know now computer scientist trees have their route at the top and the leaves down at the bottom
Here's a leaf the a upper end and here down by the multiply is the B and the C and you can very easily
see
Why that's the case
particularly if you think about this whole thing as being
driven by the
Operands not the operators
imagine that the a is knocking on the door the plus C go on add me to something and the plus is
kind of saying well
I can't because I've got to know what the right operand is and I can't
know what the right up around is until it reports back to me and says what the
intermediate answer from its expression is so again think of the be
Interrupting the multiply operator and say we ready we're ready multiplies together
So the multiplier does its work and it then passes its results up the tree to the plus that can finally do the whole thing
So therefore if that's the shape for that one
What about the shape for this one? The thing that gets done last is the operator at the top of the tree?
Look the different trees
the reason
That this gets different reverse polish gets a different answer even in the vast majority of cases here
is that the tree shapes are different and once you've said ah
So it's all down to the tree shape. I draw. Yes it is because here comes even more hidden fat chick from
the tree
You can work out what the forward polish and that the reverse
Polish will be you don't need to just pick it out of thin air as I did last time start here
You go anti-clockwise
Walk around it anti-clockwise as I start this walk I keep looking to my left if I see an operator
Can I write it down? No, you can't you can't write down an operator until you've seen all of its operands in all their glory
However, as you walk around here
Looking to the left all the time hug the tree shape as closely as you can. Look to your left. What do you see?
You see the upper and a you can always
Write down and up around come round here
Hug the tree all the time looking to your left up there. Look you see the operator. Can you write it down yet?
No, you can't you've seen it's left up around but you haven't seen it's right up around so you still can't write it down
Hug the tree look to your left. Oh, there's a new operator multiplying. Can you write it down? Nope?
You haven't seen its operands so you can't write it down
Hug the tree keep looking to the left. You see the bee. Can you write it down?
Yes
You can always write an opera Mandor down round the corner still hugging the tree
See the multiply looking to the left for the second time
Still can't write it down. You've seen one operand you haven't seen the other. So ignore it for the moment
Look to the left. You see the sea you can write it down
Nearly round the tree now come around here. Remember always looking to the left. Ah
Now you see the star. Can I write it down? Yes, because I've seen both of its operands
Finally here are a big take up at the top. You look to the left. You see the plus. Can you write it down?
Yes, you can because you've visited all of its operand structure. It's as simple as that
So if you've got the tree, you've got the postfix
You might like to try walking round the tree
wise and doing the same thing, but by looking to the right all the time as the clockwise Traverse gives you
forward
polish prefix in
Reverse and just to do your heading
to be very clear that forward polish in Reverse is not the same as
reverse polish, which is that
You get the tree?
You can derive implicitly or explicitly
postfix for use internally in working out your register usage or
if you're in an interpreter for
Implementing execution on the stack trees lead to reverse polish
Quite automatically just by walking round them in the correct way
If you get a choice of either that pair or that pair of thirds it doesn't matter wait
The system works look at that