Data Structures and Algorithms I

Program 1 - Infix Expression Calculator

This program will read a series of arithmetic expressions in infix notation. Each expression will be evaluated and the result displayed. The main Java technology used will be String and List operations. The algorithim used will reflect the normal brute force approach humans apply to this task.

All data and operations will be confined of the set of Integers. The operation *, /, %, +, and - are the only ones recognized, with the usual precedence rules. Parentheses will be allowed as well. All input will be assumed to be legal, so no error checking needs to be done.

Each line of the input file (named infix.txt) will contain an expression that is to be echoed to the console. Your program then must evaluate the expression and then add an equals sign and the arithmetic result to the output. Each line of input will correspond to one line of output. Stop the program when there are no lines remaining in the input stream.

You must implement and utilize the following classes.

TokenType
This is an enumerated type definition for the type of a token. Place this in its own file. Provide for the following values: NUMBER, OPERATION, L_PAREN, R_PAREN, and ILLEGAL. You should not need to use ILLEGAL since all of the data will be valid, but you should provide for this just in case.

Token
There are 2 constructors. The first accepts a single character (char) representing a parenthesis or operation. The second accepts a String object representing an Integer. The Token objects must store the argument to the constructor and be able to report the following:

  1. the original data provided to the constructor (as a String with leading and trailing blanks removed)
  2. the type of token (number, operation, left or right parenthesis)
  3. the value of the token if it is a number (as an int) or 0 if it is not a number
  4. a token containing the numeric result of operating on two number tokens if the token is an operation (two tokens, the operands, must be passed to this method)
  5. equals - (overrides equals in Object) reports true if the two tokens match (you can compare the Strings in the tokens).

InfixEvaluator
The constructor accepts a String representing an infix expression. This must be stored as given and converted to a list of Tokens. There is a private method that will help accomplish this second part of the initialization task.

The class must implement the following public methods:

  1. a method to return the original expression as a String
  2. a method to compute and return the value of the expression as an int. This relies on the other two private methods.

There are also several private methods:

  1. a method to parse the original expression, resulting in an ArrayList of Tokens that are then used to evaluate the expression.
  2. a method to collapse a parenthesized expression found inside the ArrayList. That is, locate and replace a parenthesized sub-expression with the equivalent value. This modifies the underlying ArrayList. (Hint... search for a ")" then work backwards to the matching "(")
  3. a method to evaluate simple expressions (those containing no parentheses). This will be applied to the ArrayList and will be accomplished by repeatedly identifying the first operation to be evaluated in the expression and then replacing it (and the adjacent operands) by a single number Token representing the result. The ArrayList (and hence the simple expression) will thus be fully evaluated.

Be sure to document every class and method (including the class supplied for you). Include a printed UML diagram for this project. Don't forget to check the documentation standards and include the signed cover sheet with your printed submission. Follow submission instructions on the assignment page.