COMPUTING SCIENCE 210
Algorithm Analysis and Data Structures

Programming Assignment 1
Infix Expression Evaluation

Due Date: Wednesday, October 19 (by midnight)

Objectives

• To gain understanding of how an implementation of an ADT is used by an application program.
• To learn how expressions can be evaluated at run-time.
• To become familiar with how infix expressions can be converted to postfix expressions.

Assignment

Write a Java program (a collection of Java classes) including a class named ExpressionCalculator that contains a static main method. This main method will prompt the user to enter a constant expression (i.e., a mathematical expression without variables) at the keyboard. The expression must be in infix notation and must use spaces to separate the tokens (operands and operators) of the expression. (This restriction is imposed to simplify the parsing of the input.) The only exception to the space-separation rule is for the unary minus prefix operator, which will be assumed to be part of the specification of a negative constant operand. The program will then evaluate the expression and display the result on the console. It will then wait for another expression to be entered for evaluation, terminating on an empty input.

The following operators should be supported by your expression calculator:

The algorithm for the infix-to-postfix converter is as follows:

   while there are more tokens in the infix string
      get the next token
      if  the next token is an operand
         append it to the postfix expression
      else if the next token is an operator
         process the operator (see below)
      else
         indicate a syntax error
   pop the remaining operators off the operator stack and append them to
   the postfix expression, but indicate a syntax error if a '(' is found

The algorithm for processing an operator is:

   if the operator stack is empty or
   the item on top of the stack is '('
      push the current operator onto the stack
   else
      fetch the top operator on the stack
      if the precedence of the current operator is greater than
      the precedence of the top operator from the stack
         push the current operator onto the stack
      else
         while the stack is not empty and 
         the operator on top of the stack is not '(' and
         the precedence of the current operator is less than or equal to
         the precedence of the top operator on the stack
            pop the top operator off the stack and append it to the postfix expression
            if the operator stack is not empty
               fetch the top operator from the stack
         if the operator on top of the stack is '('
            pop the top element of the stack
         if the current operator is not ')'
            push the current operator onto the stack

Both of these algorithms are based on the ones given in Objects, Abstraction, Data Structures and Design using Java by Koffman and Wolfgang (Wiley, 2005). One or both of them will have to be adjusted to allow for the correct processing of right-associative unary operators.

No algorithm is provided for the postfix expression evaluator, because it is relatively straightforward.

Hints

Use a StringBuffer or the new StringBuilder class of Java 5 for the postfix expression as it is being constructed. It is more efficient to make many modifications to a StringBuffer or to append() strings to a StringBuilder than to continually create new Strings by appending to existing ones.

Use Java's StringTokenizer or the new Scanner class of Java 5 to parse expressions. The latter offers the methods hasNextType and nextType (where Type is replaced by Integer, Double, etc.), which would be convenient for checking if the next token in an expression can be parsed as a Double and is thus an operand.

You may use the following Operator class, provided for your convenience, if you like:

Operator.java

Submission

Please hand in a hardcopy listing of your solution to this assignment (to ensure that the formatting which you carefully prepared is preserved) and submit the source for your solution using the following form. You may submit a solution multiple times if you wish to correct errors in previous submissions. Your last submissions will be accepted for grading.

If your solution consists of multiple Java source files each implementing a different class — and it should — use the form below multiple times, once for each source file. One of your files must be named ExpressionCalculator.java and must define an ExpressionCalculator class that includes a static main method.

Late Submissions

Assignments will be accepted after the due date and time, but late submissions will be assessed a penalty of 1% per hour or portion of an hour.

Web Password

Your assignment submissions are password-protected. These passwords apply only to form data submitted via the Web server. They are separate from (and typically different from) your network password or the password for your Unix account. To change your Web password, press the following button: