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 TASK 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.