Representation and Evaluation of Arithmetic Expressions
(HSM Ch.3.6)
- Compilers convert the infix expressions used in programming
to postfix expressions, and generate machine code to
evaluate them at run time.
- Postfix notation
(HSM Ch.3.6.2)
- In infix the operator is written between the operands. E.g.,
A * B + (C - D / E)
- In postfix the operator is written after the operands. E.g.,
AB*CDE/-+
- In postfix no ()s are needed, i.e., the evaluation is
unambiguous and does not rely on operator precedence.
- Converting infix to postfix
(HSM Ch.3.6.3)
- By hand, add ()s to all subsexpressions, then move the
operators to the position of the corresponding ), and delete
the (s. E.g.,
A * B + (C - D / E)
((A * B) + (C - (D / E)))
((A B* (C (D E/-+
A B* C D E/-+
- By a program
Initialise stack
Read symbol ch
While not end of expression
If ch is an operand
Append it to the postfix
If ch is (
Push ch
If ch is )
Pop stack
While popped value is not (
Append popped value to postfix
Pop stack
If ch is an operator
While stack not empty, and
top of stack != (, and
priority of top of stack >= priority of ch
Pop stack
Append popped value to postfix
Push ch
Read symbol ch
While stack not empty
Pop stack
Append popped value to postfix
-
| Infix
| Stack
| Postfix
|
A * B + (C - D / E)
| Empty
|
|
* B + (C - D / E)
| Empty
| A
|
B + (C - D / E)
| *
| A
|
+ (C - D / E)
| *
| AB
|
(C - D / E)
| +
| AB*
|
C - D / E)
| (+
| AB*
|
- D / E)
| (+
| AB*C
|
D / E)
| -(+
| AB*C
|
/ E)
| -(+
| AB*CD
|
E)
| /-(+
| AB*CD
|
)
| /-(+
| AB*CDE
|
|
| +
| AB*CDE/-
|
|
|
| AB*CDE/-+
|
- Evaluating postfix
(HSM Program 3.18)
The Queue ADT
(HSM Ch.3.3)
- A queue object is an ordered collection of zero or more
elements of some type, such that elements can be added only at
one designated end called the rear, and removed
only at one designated end called the front.
- Operations include initialization, enqueue an item onto
the rear of the queue, dequeue an item from the front
of the queue, check if the queue is empty or full, look at the
element at the front of the queue.
- Trying to dequeue an item off an empty queue is called
underflow.
- Whilst a queue is conceptually unbounded, in implementation the
maximum number of elements on a queue may be fixed - thus eventually
successive Enqueues (without matching Dequeues) will cause the
stack to overflow.
- As the first item enqueued onto a queue is the first item dequeued
from the queue, queues are also known as FIFOs (first in,
first out).
- Applications
- Cars in a circular driveway
- Job scheduling in the operating system (HSM Example 3.2)
- Simluation, e.g., the dreaded car wash simluation
- Naive array representation
- A front index points to the item at the front of the queue;
initially front = 0.
- A rear index point to the last item on the queue; initially
rear = -1.
- When rear + 1 == front, the queue is empty.
- When items are enqueued, the rear index is incremented.
- When items are dequeued, the front index is incremented.
- When rear + 1 == QUEUE_SIZE, the queue is full.
- What to do when the rear index reaches the last array index?
- Shift everything down to the bottom of the array.
- Move the rear index round to the bottom of the array.
- Circular array representation
- A front index points to the item at the front of the queue;
initially front = 0.
- A rear index point to the last item on the queue; initially
rear = -1.
- When (rear + 1) % QUEUE_SIZE == front, the queue is empty.
- When items are enqueued, the rear index is incremented
modulo QUEUE_SIZE.
- When items are dequeued, the front index is incremented
modulo QUEUE_SIZE.
- If the rear pointer wraps round to one behind the front
pointer, it looks like the queue is empty.
- When (rear + 2) % QUEUE_SIZE = front, the queue is full.
One array position is unused.
- queueclass.h
- queueclass.cpp
Car Wash Simluation