So I'm going to turn now to our next big example, a very big example. among the biggest examples in the course. And I'm going to show you how to evaluate a Polish expression. And recall that Polish notation, was invented so that you don't have parentheses. What we're used to is, a plus b in parentheses times c : " (a+b)*c". And parentheses give us a way to order operations. Order the way, arithmetic operations get done in determined order. And that the, the question of Polish notation is the ordering hasn't to deal with the operators or the expression. It's just to deals with where they are in a sequence. And the Polish Notation is the basis of some interesting evaluation architectures in hardware. So old Burroughs machines, and a lot of the HP calculators, were famous for using and expecting the user, to know Polish Notation. Parentheses, free notation. So instead of 3 + 4, we have +3, 4. I should really show 4. And that just means, apply binary plus. So the two arguments 3 and 4. And both of these are going to end up evaluating to 7. This is going to be how you would do it, on an HP. In the old days, the (HP's competitor) Texas Instruments (calculator) would have what we call ordinary, infix notation. Also, this example is an example of parsing. So that's a big deal in computer science, how to write a compiler. A big part of how to write a compiler is how to parse, a big part of computer languages are expressions. So this is intrinsically a way to write a compiler. f you can follow this logic, you're getting the essence of certain kinds of compiler writing as well. So you should have some background in this. But if you're forgetting it or never had studied it, here's what we'd call ordinary notation. It would be(9+6)*(3-2) , so we would end up with it being equal to 15. And here's the equivalent to what's called reverse Polish. So we have arguments 9 and 6. And then, binary plus comes along. And after binary 9 and 6 are on the operator stack, the result is 15. So, at that point, it's reduced to 15 comma 3 comma 2 minus "*" times. And the next thing you do is you move along, and now you have 3, 2 minus. So that changes, and now the stack is where in computer architecture terms put a 1 on the stack. And the answer would be this. And then you would get 15 times 1 and over all the sum is 15. And that's how reverse Polish works. Generally you have everything in a stack when you come upon an operand, the operand executes on whatever values are neighbour, its neighbours. And then when you're through the whole expression stack you, you've evaluated the expression in reverse Polish. So, an expression is an evaluation tree. Now again trees show up, everywhere there's trees. for a computer scientist, we're in love with trees. We love binary trees, we love min-max trees, we love expression trees. Again, parsing, expression evaluation, is all about walking around trees. All about, doing walks across nodes and trees. And again, expression evaluation trees are also trees with leaf nodes. And leaf nodes are where values reside. And then, the internal nodes tend to be operations. And so, they give you instructions on how to combine the values sitting at the leaf node. Now, this method that I'm going to describe is due to Andrew Koenig. I think the article that originally showed this example was in the OO literature if I'm recalling it right. I think 1988. So, it was a, an early article in the C++ community showing the power of virtual function, polymorphism and OO ideas. And it was such a beautiful method that I've always used it to demonstrate some critical ideas in C++. And it's very worth knowing Andrew's contributions. Andrew probably besides Bjarne Stroustrup himself is the second most important contributor to the C++ language. Its development and its methodology. And Andrew has written More than one super good book about programming in C++. So it's, it's well worth it for you to get familiar with his work. either find it online. Or, purchase some of his interesting, books. So again, here is Reverse Polish. here's an expression evaluation tree and what I'd like you to do is walk this tree and see what, its value would be. This is its fully parenthesized version of the tree. And here is its, what the reverse polish would look like. So we get 6, 4, and 5, and then we have plus. And when we have plus, we'll get an evaluation and we continue with the top most evaluation of the tree being here. So you can see how this maps into the tree. So take a second. And compute this tree. So walking a tree, we're going to get Plus 4 5. That's going to be equal to 9, we're going to do a times here. 9 times 6, that's going to be equal to 54. We're going to do a minus, what we get here into the tree. 54 minus 25. That's going to be 39 if I'm getting this right. And then we go over to this side of the tree. If 2 plus 3 is 5. And now we have 39 divided by 5. So, that's what, 7.8, if we're in, if it's in double. We're done. So, that's its evaluation. That's how we can walk the tree, and see what it's value is, and that's the expression tree. That's equivalent to the Reverse Polish, again hopefully this is not a new idea for you, as I said. Should have had much of this coming into the course.
