# Lab 3  An Infix Calculator

### CSCI 151 Fall, 2018 Due:  11:59 pm, Sunday, October 7

In this assignment, you will implement the computational engine of a GUI-based infix calculator.  The purpose of this lab is to:
• Learn two important algorithms for manipulating arithmetic expressions
• Gain experience in the use of stacks
• Get more experience with the use of inheritance in object-oriented programming

## Background

The application you will be working with is a simple integer calculator.  The calculator performs the arithmetic operations +, -, *, /, and ^ (exponentiation).  It also supports operator precedence and parenthesized expressions.  The calculator interface looks like this:

The user can click on the calculator buttons to create an arithmetic expression in infix form, or type an expression directly into the entry field.  When the expression is complete, the user can either click on the "=" button or hit return in the entry field to produce a result, which then appears in the entry field.  I'm providing the code for the Calculator GUI, which you can find in the startup file for this lab, lab3.zip.

Calculator.java contains the action listeners for the entry field and all the calculator buttons.  Their actions are:
• digit and operator keys.  As the user hits these keys, digits and operators are added to a string representing the infix form of an expression, which is displayed in the entry field.
• clear key.  It clears all the fields.
• = key and entry field. The entry field displays the input as it is keyed in by the user (either through the Calculator keys or the computer keyboard.)  When the user hits the return key on the keyboard or the "=" key on the Calculator,
• the string in the entry field is converted to a list of Tokens in infix format
• the infix token list is converted to a list of Tokens in postfix format
• the postfix token list is converted to an Expression object
• the value of the Expression is displayed in the entry field
• the infix, postfix, and prefix forms of the Expression are displayed in the corresponding fields.

The main program of the application is found in Calculator.java.  It creates the GUI and displays it, then waits for input from the user.

## Objects

The program is based on an object-oriented view of the calculator's operations, using objects to represent Tokens and Expressions.

### Token

An arithmetic expression entered by the user is a sequence of Tokens.  There are two types of token:  Operators ( +, -, *, /, ^, (, ), or = ) and Numbers (nonnegative integers in decimal notation).  In our program, Token is an interface with two implementing classes:  Operator and Number.  I'm providing the code for these in the lab3.zip file.

### Expression

The program is going to take a list of tokens entered by the user and build an Expression object, which incorporates the structure of the expression.  From the expression object, it's quite easy to determine the value of the expression and to display it in infix, postfix, or prefix form.  Expression is an interface with the following methods:

public int valueof();
public String toPrefix();
public String toInfix();
public String toPostfix();
public String toString();

There are two implementing classes:  Number and BinaryExpression.  Note that Number implements both Token and Expression, so we'll be able to treat it as a Token in one part of the program and Expression in another part. (This is called multiple inheritance, which Java allows for interfaces but not for abstract classes.)

Your responsibilities are to write the Expression classes, and the ExpressionManager class (which contains the infix-to-postfix and build-expression methods).

## Startup code

I've supplied starting point code here:  lab3.zip.  To get Eclipse working with these you should do the following:
1. Create a lab3 folder
2. Unzip the startup code into your lab3 folder
3. Start up Eclipse (remember to use the same workspace you set up in lab 1)
4. Create a new Java project in Eclipse; make sure that the "Location" in the setup page is your lab3 folder
5. You should now see a number of files in the default package for the project.

## Part one - the Number and BinaryExpression classes

An expression can be either a number, or a binary operator applied to two subexpressions.

### Number

The version of Number in lab3.zip already contains the code to implement the Token interface.  You need to add some methods to it so that it also implements the Expression interface.

First, modify the header line to indicate that the class implements both Token and Expression:

public class Number implements Token, Expression {

Then write the valueOf, toInfix, toPrefix, toPostfix, and toString methods which are required by the Expression interface.  The value of a number is simply the integer value of the number, which you have as an instance variable (so just return it).  The other four methods can all return the same value:  the String representation of the number.  (You can get the String representation of a number by concatenating it with an empty String, or by calling Integer.toString)

### BinaryExpression

Write the BinaryExpression class.  It implements the Expression interface.  It has an Operator and two Expressions (its left and right operands) as instance variables.  (Note that this is a recursive definition.)

Write a constructor with an operator and left and right operands as parameters.

Write the valueOf method.  It should evaluate the two operands and apply the operator to the results to get its result.  (You can call the apply method in the Operator class.)

The toPrefix method should return a string consisting of the operator followed by the prefix representations of the left and right operands.  (Because you may be dealing with multidigit numbers, you'll have to separate the items by spaces in both toPrefix and toPostfix.)

The toPostfix method should return a string consisting of the postfix representations of the left and right operands followed by the operator.

Because of the inherent ambiguity of infix notation, the toInfix method should generate a fully parenthesized infix representation of the expression; for example, ((3+5)*(12+7)).  So the infix method should generate a string with the left operand, operator, and right operand enclosed in a pair of parentheses.

toString should produce exactly the same String as toInfix.  In fact, it can simply make a call to toInfix to get its result.

Note that all of the methods in BinaryExpression are essentially recursive, but the base cases are found in the Number class.

### Testing

Test your Expression class with JUnit tests.  In your tests, create several example expressions, call their methods, and then make assertions about the results.  Here is a start:

Expression e1 = new Number(46);
assertEquals("e1",46,e1.valueOf());
Expression e2 = new BinaryExpression(new Operator("/"),new Number(120),new Number(7));
assertEquals("e2",17,e2.valueOf());
Expression e3 = new BinaryExpression(new Operator("-"),new Number(50),new Number(15));
assertEquals("e3",35,e3.valueOf());
Expression e4 = new BinaryExpression(new Operator("*"),e2,e3);
assertEquals("e4",595,e4.valueOf());

You should add a few more expressions and also test the toInfix, toPostfix, and toPrefix methods.

## Part two - Write the Expression Manager class

The Expression Manager must implement two methods:  infixToPostfix and buildExpression.

public List<Token> infixToPostfix(List<Token> infix);
public Expression buildExpression(List<Token> postfix);

Use the stack-based algorithms presented in class to write these methods.  You may use the Stack class found in java.util.

### buildExpression

The buildExpression method is the simpler of the two.  I recommend writing it first.  The method is based on the "evaluate postfix" algorithm presented in class.  However, instead of evaluating the postfix expression directly, it uses the postfix expression to construct an Expression object.  You can do that by making the following modifications to the postfix evaluation algorithm:
• The stack is a stack of Expressions instead of a stack of operand values.  (Use a "Stack<Expression>".)  (Note:  Stack is a Java class found in the java.util package, so you'll need to import java.util.Stack)
• When you get a Token from the postfix List, you have to decide whether it's a Number or an Operator, and then cast it to the appropriate type.  (Note:  The Token class has methods isNumber and isOperator to let you test whether a given Token is a number or an operator.)
• If it is a Number, you can just push it onto the stack.  (It's already an Expression.)
• If it is an Operator, pop two operand Expressions from the stack, create a BinaryExpression from the operator and the two operands (i.e., call the constructor), and push it onto the stack.
• When you reach the end of the postfix list, there should be one Expression on the stack.  That's the expression that the algorithm has built.  Pop it from the stack and use it as the the return value from the buildExpression method.
When you've completed it, write some JUnit tests to test it out.  Here is a start.  You should write more.

ExpressionManager expressionManager = new ExpressionManager();
ArrayList<Token> postfix = new ArrayList<Token>();
Expression e1 = expressionManager.buildExpression(postfix);
assertEquals("build test 1",37,e1.valueOf());
postfix.clear();
Expression e2 = expressionManager.buildExpression(postfix);
assertEquals("build test 2",260,e2.valueOf());
assertEquals("build test 3","(20*13)",e2.toString());
assertEquals("build test 4","* 20 13",e2.toPrefix());

### infixToPostfix

The infixToPostfix method uses the concept of operator precedence described in class.  I've included a method in Operator to set the priorities for each of the operators.  The method should use a Stack<Operator>.  You can use a for-each loop to step through the elements of the infix list.

Now write the infixToPostfix method.  Here is a sample JUnit test:

ExpressionManager expressionManager = new ExpressionManager();
List<Token> infix = new ArrayList<Token>();

List<Token> postfix = expressionManager.infixToPostfix(infix);
Expression e1 = expressionManager.buildExpression(postfix);
assertEquals("infix to postfix test 1",7,e1.valueOf());

You should write additonal test cases.  In particular, write tests that will check your handling of parentheses and operator precedence.

### Programming notes:

• You are required to handle parenthesized expressions.
• One flaw in the algorithm I provided you is that the exponentiation operator (^) should have right-to-left associativity.  See if you can fix the algorithm to handle it properly.

## Part three - Error handling

When a user uses your calculator, it's possible that an invalid expression will be entered into the entry field.  Some common errors in infix expressions are:

• mismatched parentheses
• missing operator symbol where one is expected
• missing number where one is expected

You should anticipate and handle as many of these errors as you can.  Each time you detect an error in either the infixToPostfix or buildExpression method, throw an ArithmeticException with an appropriate error message, like this:

throw new ArithmeticException("Mismatched Parentheses");

Some errors will cause exceptions in the expression manager, such as an EmptyStackException.  In those cases, you should catch the EmptyStackException and throw an ArithmeticException.  Other errors may not result in an exception; try to identify those, too, and throw an exception.  You may not be able to catch every possible error, but try to handle as many as you can.

Calculator.java contains a try-catch statement (lines 168-181) to catch the arithmetic exceptions.  Notice that I'm only catching ArithmeticExceptions; you need to make sure that whenever an error occurs in the user input, an ArithmeticException gets thrown.

## handin

The directory you submit through handin should include all of the files needed to run the Calculator (including the ones I provided) , and a README file.  Look through each of the files you've written or modified and make sure you've included your name at the top of all of them.  The README should include a statement of any known problems in your code.  If you adhered to the honor code in this assignment, add the following statement as a comment at the top of your README file:

I have adhered to the Honor Code in this assignment.

Quit Eclipse, and then go through and delete any *.class files and backup files.  (If you don't quit Eclipse first, it will keep regenerating your class files when it autocompiles!)

You now just need to electronically handin all your files.

```    % cd          # changes to your home directory
% cd cs151    # goes to your cs151 folder
% handin      # starts the handin program
# class is 151
# assignment is 3
# file/directory is lab3

% lshand      # should show that you've handed in something
```

You can also specify the options to handin from the command line

```    % cd ~/cs151                 # goes to your cs151 folder
% handin -c 151 -a 3 lab3

% lshand      # should show that you've handed in something
```