Class Notes (1,100,000)
CA (620,000)
Queen's (10,000)
CISC (500)
Lecture 8

# CISC 235 Lecture Notes - Lecture 8: Reverse Polish Notation, Polish Notation, Binary Tree

Department
Computing
Course Code
CISC 235
Professor
Robin W Dawes
Lecture
8

This preview shows pages 1-2. to view the full 8 pages of the document.
CISC 235 Lecture 7 & 8
Postfix, Prefix and Infix Notation
In our discussion of stacks we briefly looked at postfix notation
for arithmetic expressions. when an expression is written in
postfix notation, it can be evaluated in left-to-right order - we don't
need to apply any precedence rules for the operators. When an
operator is encountered in the left-to-right order, we apply it to the
two values that immediately precede it then put the result into the
expression to replace the operator and its operands.
For example, the postfix expression
3 4 + 8 * 5 2 - *
is evaluated (showing all the stages) as
3 4 + 8 * 5 2 - *
7 8 * 5 2 - *
56 5 2 - *
56 3 *
168
The notation that most of us have grown up with is formally
called infix notation: operators are placed between their operands,
and we use parentheses and precedence rules to control the order
of evaluation.
The expression above, in infix notation, would be
(3 + 4) * 8 * (5 - 2)

Only pages 1-2 are available for preview. Some parts have been intentionally blurred.

We need the parentheses because if we just wrote
3 + 4 * 8 * 5 - 2
our standard precedence rules would give a different result.
This illustrates the idea that postfix notation is shorter than infix
(no parenthesis) and easier to evaluate (it's just left-to-right).
For Lukaseiwicz (who was focusing on logic rather than arithmetic
at the time), postfix notation was not as interesting as prefix
notation.
In prefix notation, the operators come first, followed by their
operands. For example the expression we have been working with
could be expressed in prefix notation as
* * + 3 4 8 - 5 2
When evaluating a prefix expression, we can also work from left to
right. When we encounter an operator we "hold onto it" until we
have the values of its operands. So the stages of evaluation of this
expression are
* - hold it
* - hold it
+ - hold it
3
4 - now we have two operands, we can compute + 3
4
7
8 - now we have two operands, we can compute * 7
8
56
- - hold it

Unlock to view full version

Only pages 1-2 are available for preview. Some parts have been intentionally blurred.

5
2 - now we can compute - 5 2
3 - now we can compute * 56 3
168
Prefix notation corresponds to a functional programming
approach. We can think of * * + 3 4 8 - 5 2 as representing the
functional expression
product(product(sum(3,4),8),difference(5,2))
It is a very valuable exercise to consider how we might use a
stack to evaluate an expression in prefix notation.
To segue from our study of stacks to binary trees, I suggested that
a binary tree can be used to store an arithmetic expression in such a
way that any of the three representations can be produced. Before
we see that (which is a very minor application of binary trees) we
must first define them carefully.
Binary Trees
Binary Tree: a rooted tree in which each vertex has at most two
children. The children (if any) are labelled as the left child and the
right child. If a vertex has only one child, that child can be either
the left child or the right child.
Binary trees can also be defined recursively:
An empty tree is a binary tree with root = Null.
A single vertex is a binary tree with root = the single vertex.