Last update: June 28, 6:00PM.

Note: No late homework will be accepted.

Note: You are responsible for reading and understanding the course policy on academic integrity. Re-read it before continuing, especially the parts relevant to programming.

Note: This is a long handout. Read it thoroughly and highlight things so you don't forget to do part of the assignment.

Purpose

The purpose of this assignment is to make you learn Java, some various aspects of object-oriented programming, and the implementation of some simple data structures. With this first programming assignment, we will provide a fair amount of code and guidance, and you will be graded a fair amount on style. In fact, getting something that works should not be too hard. But you should take the time to write something that is elegant and straightforward.

Overview

• All numbers are integers. (Actually ints, as defined in Java. That is, don't worry about overflow.)
• There are four binary operators: "+", "-", "*" and "/". They add, subtract, multiply, and divide two numbers respectively. Division means integer division, as in Java.
• There is one unary operator: "~". It means negation. We have made life easier by using a different string than we use for subtraction.

1. A postfix calculator (Calculator.postfixEval)
2. A prefix calculator (Calculator.prefixEval)
3. A prefix to InfixTree translator (Calculator.prefixToInfix)
4. An InfixTree calculator (Calculator.infixEval)
5. An InfixTree expression printer (Calculator.infixString)

Infix, Postfix, Prefix

• Infix: ((3 + (~4)) * 7)
• Postfix: 3 4 ~ + 7 *
• Prefix: * + 3 ~ 4 7

Data Structures (big hints)

For the postfix calculator, you will want a stack of integers. You may not use the Java Stack library; you should write your own. It is not necessary to write a polymorphic stack like we discussed in class. For the prefix calculator and prefix to InfixTree translator, you will want to use recursion. (This is just an implicit stack -- see food for thought.) You need to write the InfixTree data structure. This is where object-oriented design comes into play -- think about what kinds of infix trees there can be and have them extend the same abstract class. The InfixTree calculator and expression printer can be simple recursive tree walks, although it may look superficially different in an object-oriented setting.

Getting Input

The functions postfixEval, prefixEval, and postfixToInfix all take a TokenReader object as input. We provide TokenReader for you. Just think of a TokenReader as a sequence of Strings. To get the next String, call the readString() method. If you call readString() but there is no next String, then the eof() method of the TokenReader object will return true. (Notice that you have to call readString() "one too many times" for this to happen.)

If the next String is an integer, readString() will return a String of digits, not an integer. That is, "123" will be a String of length 3 whose first element is '1', etc. To convert this to an int, use the function Integer.parseInt(String s) provided by Java. If you pass a String that does not represent an integer, then it will throw a NumberFormatException. Your program should catch this exception and act appropriately.

The main method in the code we provide you works like this: It takes two command-line arguements. The first must be "post" or "pre". The second must be the name of a file. The contents of the file should be a single complete expression in postfix (if the other argument is "post") or prefix (if the other argument is "pre"). main will create a TokenReader from the file and test the appropriate methods. The lines that call the methods are commented out -- you should uncomment them after you write the methods. There is nothing particularly magical or complex about main; you should understand it since we will probably not provide such code for future assignments.

Be sure to read the Developer Studio information on how to change project settings. Specifically, you will need to set Calculator as the class for debugging/executing, set stand-alone interpreter as the way to execute the program, and set the command-line arguments as described above. If you forget to do any of these things (or do them wrong), only strange unhelpful things will happen.

Dealing with Errors

You should expect each input file to contain exactly one complete expression. If it contains more than one, then it is acceptable to return the result of only one of them. (You will find that for prefix you'll return the first and for postfix the last.) If it contains an error (either because it has an incomplete expression or because it has a String which is not an integer or an operator), then you should throw a CalculatorIllegalInputException.

All of your calculators must also check for division by zero. If it is encountered, then you should throw a CalculatorDivideByZeroException. This exception should not be thrown by prefixToInfix.

This is not a hard part of the assignment; we're simply requiring you to make your program a bit more robust.

Code we're providing you

• Calculator.java (Lots of holes for you to fill in.)
• InfixTree.java (Abstract class; don't modify this file)
• TokenReader.java (Don't look at this; just use it as described above)
• CalculatorDivideByZeroException.java
• CalculatorIllegalInputException.java

The exception files are provided since naming new exceptions is just tedious. Of course, you will have to create some other files, specifically those for implementing integer stack and infix tree data structures.

What to Turn In

• A floppy diskette (with your name on the outside) with all of the relevant files (Dev. Studio project files, .java files, .class files) including the files we provided you.
• A monospaced-font printout of all your .java files (including Calculator.java, but excluding the other provided files).

Make sure your code is well-documented. This should include a description of the role of each class in the program. Also, if your program does not work, describe its shortcomings.

Extra Credit

• ~ has higher precedence than * and / which have higher precedence than + and -, for example 2 * 3 + 1 could replace (2*3) + 1.
• +, -, and * are associative, for example 2 * 3 * 4 could replace ((2*3)*4) or (2*(3*4)).
• Notice however, that / is NOT associative! Since in integer division ((4/2)/3) does NOT equal (4/(2/3)), we can replace neither with 4/2/3. The same is true with ((4*2)/3) and (4*(2/3)). Precedence still holds, though, so we can replace (1+(2/3)) with 1 + 2/3.

For extra credit, write a infixStringEC which prints only necessary parentheses. Hint: Do not call infixString and then try to remove parentheses. Generate a new String from scratch that gets it right the first time.

Food For Thought

• Why would it be hard to use recursion for postfixEval?
• Why would it be hard to use an explicit stack for prefixEval?
• Infix needs parentheses to avoid ambiguity. Otherwise we couldn't distinguish (1+2)*3 from 1+(2*3). It turns out, though, we can get by with deleting all of the close parentheses and still not have ambiguity. We just leave them in for human readability. Proving this requires a pretty tedious induction and is beyond what we're interested in here.