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

54 ratings

University of California, Santa Cruz

54 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 here we have another abstract base class. It's a leaf node, it's going to be defining itself in terms of the base class node, another abstract class. So you can have an abstract class inherit from an abstract class. And again we see why it is abstract because the print functions

and the evaluation functions are still undetermined. They are still without definition, and LeafNodes are going to be derived from this. In which the different kinds of leaf nodes will again, the terminology is, we'll need to override.

And the concrete, so we need to derive from LeafNode to a concrete kind of LeafNode, and then these will have actual implementations.

Let's look at one. This is probably our simplest one. This is where we have a constant. If we have an expression tree which is a constant, It’s its own value. So imagine having six sitting there without any operations, the value of that expression is six. And look at what the semantics are for the overwritten functions. We just print the value.

constructor of an int node. And here's our evaluator. We just return, print the value, and the value is itself.

So you're thinking of a node at the tree looking like seven. If we call the print function, which is seven. If you, if you called the eval function, you would get the value seven. Trivial case. How about a variable? And again, variables, the way I'm going to do this.

It's a very simplified version. And we're going to say that ASCII character. an ASCII arithmetic alphabetic character. like A is going to be a variable, and we're going to show that at some point what is stored is it's value. So, it's going to be inside a value, and then the index is going to be its name, and the name is going to be this ASCII character.

But the evaluation would be whatever is stored there. If I stored 3 there, this would evaluate to 3. It would print A, evaluate to 3.

Here's a unary node. Unary node, for example, is unary minus. So that's unary node. If we had a larger expression syntax that allowed Booleans.

I can see somebody there shouting at me over the Internet that it's negation. So, negation is a unary Boolean operator. We're just doing arithmetic operators, so we're going to probably just stick with minus and plus. Plus is effectively a null op. This plus of 5 is still 5, -5, is the inverse to, to ordinary 5. And let's again look at what things are going to happen. we of course have a constructor for it. And this is what it's infix is going to look like. What we're going to print, includes this, is, let's say the operator is minus. Let's say the operand is for example, A,

minus A, and the evaluation of it we'll see in a second. Will end up being minus whatever the value of that expression was. To first call the evaluation and then apply the appropriate operator. So here it is.

We take the operand. If it's minus, if the case is minus, We do minus operand.evaluation. If the case is plus, we just do ordinary plus. Or we could have just said opnd.eval. [INAUDIBLE] It's just a simple switch.

More interesting case, binary operators. So, arithmetically again, binary operators, think about what they are. Plus, minus, times, lots of binary operators.

In a binary operator case, we're going to apply it to a right tree and a left tree. So, here's a binary operator, let's try and draw one like plus. And here's going to be one tree, tree left and tree right. And recursively, all of this is going to work both polymorphically and recursively. Recursively, we're going to walk the left tree, we're going to get its parenthesized print out and its evaluation. We're going to walk the right tree and do the same thing, and then we can combine them using the plus operation.

Get whatever is on the left, and then fully parenthesize it. So there's a bunch of stuff, then there's your operator, plus, then there's a bunch of stuff. And so whatever stuff ended up in here, which is probably also parenthesized, shows up and you get an appropriate, fully parenthesized expression. And then eval, is again going to be a big switch that also is going to work recursively. So here's eval. And you can see in this particular case that I've done it for three binary ops, and these examples can be extended. So, if you have an interest in this, you can readily extend this to the more a much fuller expression, evaluation scheme for C++. And notice, here's your critical, if you want to think of it as your recursion.

You do your left eval, you do your operator, which in this case is minus, and here are the actual semantics. And then you do your right eval.

So these are going to call appropriate routines. These are your pointers or your trees. They'll all be done, and then they'll go down to whatever level actually, typically ends up being a leaf node. Which could be concretely a constant value or a parameter in which you have to look up the constant value. So it's all going to work seamlessly, and it's easily extensible.

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