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