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

来自 University of California, Santa Cruz 的课程

C++ For C Programmers, Part B

72 个评分

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.

从本节课中

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.

We print n to the output. And this is our initializer, or our

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.

So if I have A I can look up

the value with this it's almost like an associated array.

And here I print the name.

So, if I print, this print function, this would look like the tree

A.

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.

what would be a Boolean?

Somebody out in the audience, what would be a Boolean unary operator?

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,

so we would print out the parenthesis expression,

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.

So, you can see how they print.

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.