CIS 180: Object-Oriented Programming
Homework #5
Prefix Expressions
Due Monday, October 19, 2009
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:
Click Here to Download
Import the Prefix project into your eclipse workspace:
- Choose "Import..." from the "File" menu.
- Open the "General tab", select "Existing Projects Into Workspace", then click "Next".
- 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. 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. The only
changes you make should be to add code.
- 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:
- 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.
- The UML class diagram for your project.
- 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:
ttao@umassd.edu.
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.
There will be a 10% penalty for assignments received after the due date.
Assignments will not be accepted more than one week past the due date.