# CIS 180: Object-Oriented Programming Homework #5

## Prefix Expressions

### Objectives

The objectives of this homework are:
• To develop a program involving multiple classes and multiple instances of each class
• To apply the concepts of inheritance, polymorphism, overriding, and late binding

### Background

There are several useful notations for arithmetic expressions involving binary operators. The most common notation is infix notation, where the operator appears between the two operands. Another notation is prefix notation, where the operator appears before the two operands, e.g. (+ 7 4) instead of (7 + 4). Prefix notation has the advantage that there is no need for parentheses or operator precedence rules. For example, in the infix expressions (6 - (3 + 2)) and ((6 - 3) + 2) the parentheses are significant. In prefix notation these expressions would be written as (- 6 + 3 2) and (+ - 6 3 2), respectively. We could add parentheses for readability, e.g. (- 6 (+ 3 2)) and (+ (- 6 3) 2), but they are not required. For a detailed discussion of prefix notation, please read the Wikipedia entry.

### Problem Statement

For this assignment you are asked to complete a java program that allows the user to enter a prefix expression on the java console, and then prints out both the value of the expression and an equivalent expression in infix notation. An example of how the program should behave is given below (user input in blue):

```
Prefix Expression: + * 3 - 7 2 - / 27 3 * 2 4
Value: 16.0

Infix Notation: ((3.0 * (7.0 - 2.0)) + ((27.0 / 3.0) - (2.0 * 4.0)))
```

### Problem Decomposition

The project you are given to start with contains seven classes as shown in the UML class diagram below:

The diagram shows the fields and methods that are already defined. Every expression is either a number represented by an instance of NumExp, or a binary operation expression with two operands which can themselves be arbitrary expressions. The binary expressions are represented by instances of the classes AddExp, SubExp, MulExp, or DivExp depending on whether the operator is addition, subtraction, multiplication, or division. The Expression class has methods for parsing the users input and creating objects to represent the input expression. For example, if the user's input is + * 3 - 7 2 - / 27 3 * 2 4, the parser will build expression objects with the following structure:

The Expression class has public methods getValue to return the value of an expression, and toInfix to print the expression on the java console in infix notation. You will need to override these methods where appropriate in order to get the correct results. The main method is already written for you in the Expression class. The main method prompts the user to enter a prefix expression, parses the expression to build an object tree, and sends getValue and toInfix messages to the object at the root of the tree.

### Parser Quirks

The parser code is designed to be as simple as possible and is not very robust. In particular:
• If the user input is not a valid prefix expression, the parser will print an error message, but the messages are probably not very useful in figuring out what the error was.
• You can include parentheses for readability in the input, but the parser simply ignores them. For example, it does not check that the parentheses occur in the right places or that they match properly.
• If a minus sign is followed immediately by a digit or decimal point, the parser will interpret the minus sign as part of a negative number rather than the subtraction operator, even if this interpretation results in a parsing error.

### Design

• Step 1. Add methods to the UML class diagram given above to implement the expression evaluation. You should not need to add any new fields to the existing classes and you should not add any new classes.
• Step 2. Download the zip file containing the Eclipse project for this homework from the link below:

Import the Prefix project into your eclipse workspace:
1. Choose "Import..." from the "File" menu.
2. Open the "General tab", select "Existing Projects Into Workspace", then click "Next".
3. Click the "Select archive file" radio button, browse for the zip file, make sure the Prefix project is checked in the Projects pane, and click "Finish".
• Step 3. Add methods to the UML class diagram to implement printing the expression in infix notation. Do not add any new classes or fields. Do this part only after you have successfully completed the implementation part of the expression evaluation. If you make mistakes in your design in step 1, you are likely to repeat them here. For this part, try to avoid duplicating code in the various subclasses of BinaryExpression.

### Implementation

• Do not remove or modify any of the existing code you are given. Do not add any new classes. Do not add fields to the existing classes. The only changes you make should be to add methods.
• Complete the implementation in small increments with frequent testing.
• Start by implementing the methods needed to evaluate expressions that consist of a single number with no operators.
• Next, implement the methods necessary to evaluate expressions that include the addition operator. Test thoroughly.
• Continue adding one operator at a time, testing after each addition.
• When the expression evaluation methods are complete, follow the same incremental approach to coding the printing of expressions in infix notation.

### What to turn in

When your assignment is complete, turn in:
1. A document containing an explanation of any problems you encountered in completing the assignment and describing any bugs in your solution. Undocumented bugs are worse than documented bugs. If you have undocumented bugs we will assume that you did an inadequate job of testing your code, and you will lose additional points.
2. The UML class diagram for your project.
3. A zip file containing your completed project. This should be a zip archive of the project folder from your Eclipse workspace.

The project zip file must be submitted as an email attachment to your lab instructor. Use the subject line CIS-180 HW#5 in your email. The problem report and UML class diagram may be submitted as attachments to the same email, or in hard copy.

Make sure you send your homework to the proper place. Homework sent to the wrong address may not receive credit!