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.
3.8 Polish Notation
Loading...
Del curso dictado por University of California, Santa Cruz
C++ For C Programmers, Part B
90 calificaciones
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.
Conoce a los instructores
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,
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.
