# Assignment 1: Legacy Fortran (25%)

REVERSE
POLISH NOTATION TRANSLATOR

INTRODUCTION

Ever heard of Reverse Polish Notation (RPN)? Probably not.
Algebraic notation is often termed infix
notation - the arithmetic operator appears between
the two operands to which it is being applied. This may require parentheses to
specify the order of operations. Postfix
notation, on the other hand, eliminates the need for parentheses because the
operator is placed directly after the
two operands to which it applies. This form of notation is sometimes called
Reverse Polish Notation after the nationality of its creator, Polish logician
Jan Lukasiewicz. For many years, HP has sold handheld calculators which require
input in RPN, starting with the HP-35 in 1972. It worked great, but there was a
learning curve - converting from traditional expressions to RPN expressions.
Here is a RPN expression:

!    AB+C*

The plus sign applies to the two operands to the left of it.
After doing the addition, the expression is scanned looking for the next
operator. When it is found, it is applied to the two quantities preceding it,
which are A+B and C. So this RPN expression is equivalent to the algebraic
expression (A+B)*C.
Here are some more algebraic expressions and their RPN equivalents:

Algebraic

Polish

!

A+B+C+D! !

AB+C+D+

!

A+B*C+D! !

ABC*+D+

!

(A+B)*(C+D)!

AB+CD+*

It affords a better way of using a calculator by using fewer
keystrokes. Consider the following example:

(7 + 4) / (9 - 5) = ?

Mode

Process

Keystrokes

Algebraic

1.  Calculate 9
− 5 =

2.  Store 4 in memory m+
3.  Calculate 7  + 4
=

4.  Divide 11 by 4 in memory mr =

12

RPN

7 [ENTER] 4 +
9 [ENTER] 5 −
/

9

Attached to this assignment is a reverse-polish translator
written in Fortran IV. The task is to migrate the legacy Fortran IV program
into a Fortran-90/95 program. This involves converting and removing any
structures which are relevant/irrelevant. Your code should be clean and easy to
understand (unlike the existing code). The program contains a number of
structures which should be modified or removed to make the program more
maintainable. Some examples include:

•  unstructured
statements in the form of GO TO statements, and labels.

•  Hollerith
characters which are replaced by a character string

Part of the process of re-engineering a piece of code
involves understanding what the code does. Spend some time analyzing the code
using the flowchart for the algorithm in the Appendix. This will help with
understanding how the code works.

DESIGN DOCUMENT

Discuss your re-designed program in 3-4 page design document, explaining decisions
you made in the re-engineering process. Consider the design document a synopsis
of your re-engineering process. One page should include a synopsis of the
approach you took to migrate the program ( e.g. it could be a numbered list
showing each step in the process). Identify the legacy structures/ features and
how you modernized them.

Some of the
questions that should be answered include:

•  Would
it have been easier to re-write the program from scratch in a language such as
C?

•  What
were the greatest problems faced during the re-engineering process?

•  Is
your program shorter or longer? Why?

•  Is
there a better way of writing the program?

Your program should compile using gfortran.

TESTING

The program can be tested using the following series of
algebraic expressions.

A*(B+C)

ABC+*

(A+B)*(C+D)

AB+CD+*

(A+B)*C

AB+C*

A-B/C

ABC/-

A+B*C+D

ABC*+D+

(A-B)/C

AB-C/

A/B+C

AB/C+

A/(B+C+D)

ABC+D+/

A/B/C

AB/C/

(A/B)/C

AB/C/

A*B-C+D

AB*C-D+

A*B-(C+D)

AB*CD+-

GOING BEYOND (5%)

Extend the re-engineered program to include an
exponentiation operator, represented by a ^ character, and having higher
precedence than multiplication or division.

SKILLS

Fortran programming, re-engineering through migration,
program comprehension, ability to review specifications

DELIVERABLES

Either submission should consist of the following items:

•  The
design document.

•  The
code (well documented and styled appropriately of course).

APPENDIX - RPN

The algorithms first task is to identify the various
characters as operands or operators. The operands are single letter variables.
The operators are:

!    -  + * / (
)

Then each operator is assigned a ranking (precedence) to
determine where it appears in the RPN expression. In the absence of
parentheses, multiplication and division are performed before addition an
subtraction. Otherwise the ranking is as follows:

!    (        1

!    )        2

+ -    3

* /    4

A ranking of zero identifies an operand.

The basic premise of the algorithm is as follows. Operands
are always transferred to the output string (POLISH) as soon as they are
encountered. Operators, except for right parenthesis, are always transferred to
the OPSTCK (OPerator STaCK), to await transfer to the output string. When
operators are transferred to OPSTCK, their ranking is assigned to the
corresponding element of an array called OHIER (Operator HIERarchy).

After an operand has been transferred to the output string,
a check is made to see if the last entry in OPSTCK has a higher ranking than
the next operator in the input, or the same ranking - if so, the operator from
OPSTCK is transferred to the output. Whenever a right parenthesis is found in
the input, it is ignored and the matching left parenthesis, which will always
be the last entry in the operator stack at this point, is also ignored.

The
algorithm for the Fortran IV program is shown in flow-diagram form on the next
two pages.