This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.

Loading...

From the course by University of California, Santa Cruz

C++ For C Programmers, Part B

53 ratings

University of California, Santa Cruz

53 ratings

This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.

From the lesson

Hex and the use of AI and C++ Move semantics

This module explains Min-Max and the Alpha-Beta algorithm for game playing. Its programming topics include C++ 11 Move semantics and a detailed example of referential garbage collection.

- Ira PohlProfessor

Computer Science

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,

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

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.

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.

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.

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.

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

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.