Class Notes (1,100,000)

CA (620,000)

Queen's (10,000)

CISC (500)

CISC 235 (20)

Robin W Dawes (20)

Lecture 8

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

by OC330671

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

###### You're Reading a Preview

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.

###### You're Reading a Preview

Unlock to view full version