Explore
For Enterprise
Join for Free
Log In

artes y humanidades
Negocios
Ciencias de la Computación
Ciencia de Datos
Tecnología de información
salud
Matemáticas y Lógica
Desarrollo Personal
Ciencias Físicas e Ingeniería
Ciencias sociales
Aprendizaje de un idioma
Grados
Certificados

Explorar todo lo que Coursera tiene para ofrecer

Explorar
Buscar
For Enterprise
Inicia Sesión
Únete de forma gratuita

3.8 Polish Notation

Loading...

C++ For C Programmers, Part B

Universidad de California en Santa Cruz

4.2 (103 calificaciones) | 17K estudiantes inscritos

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.

Destrezas que aprenderás

Graph Theory, C++11, Standard Template Library, C++

Revisiones

4.2 (103 calificaciones)

5 stars
61 ratings
4 stars
25 ratings
3 stars
8 ratings
2 stars
2 ratings
1 star
7 ratings

RK

Apr 05, 2019

Highly recommended for anyone wanting to learn some serious C++ and introductory AI!

SW

Jan 14, 2018

The course provides a great primer for new C++11 features.

De la lección

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.

3.8 Polish Notation8:47

3.9 Referential Garbage Collection17:13

3.10 Abstract Base Class = 0 Notation9:42

3.11 Tree Constructors8:34

Impartido por:

Ira Pohl
Professor

Transcripción

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.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play

Coursera
Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government

Comunidad
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Blog de Tecnología

Más
Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados