CIS 180: Object-Oriented Programming
Homework #5

Prefix Expressions

Due Wednesday, October 26, 2011


The objectives of this homework are:


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:



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!

Lab SectionGraderEmail
L1 Mon. 2PM Wes Fowlks
L2 Wed. 9AM Neelima Mothe
L3 Wed. 1PM Wes Fowlks

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.