CMPU 125 - Assignment 7
Algebraic Expression Conversion and Evaluation
Assigned: Friday, Oct 31
Due:  Friday, Nov 14

In this Assignment you will build an expression evaluator, using Java commands to perform file input and output. Your solution will rely on using the built-in implementation of the Stack ADT, as discussed in class and in Ch. 7 of the text. The Stack you will use is from the Java API: java.util.Stack. The expression evaluator will consist of the following classes:

Below is information you will need for implementing each of these classes.


Calculator - The Driver Program

Class  Calculator is the driver program for this project. It contains only a  main() method in which you will create InfixToPostfixConverter and  PostfixEvaluator objects.  Your main method will do the following: 

  1. open an input file containing one infix expression per line, the name of which is read from the command line, 
  2. read each infix expression in turn and pass the infix expression to the InfixToPostfixConverter, 
  3. get the resulting postfix expression from the InfixToPostfixConverter and pass it to the PostfixEvaluator's evaluate method, and 
  4. print the following strings to the output file: infix string, postfix string, and result of evaluation for each string read from the input file, in the format shown below.
Below is the actual code for the main() method in class Calculator. You will need to add the following import statements to the top of your Calculator.java file:

import java.util.Scanner;
import java.io.*;


The Calculator class main method should use the following code:

   public static void main(String[] args) {
      InfixToPostfixConverter converter;
      PostfixEvaluator evaluator;
      converter = new InfixToPostfixConverter();
      evaluator = new PostfixEvaluator();
      try {
         Scanner sc = new Scanner(new File(args[0]));
         PrintStream ps = new PrintStream(
                              new FileOutputStream(
                                  new File(args[1])));
         String infixString;
        
         while (sc.hasNext()) {
            System.out.println("reading");
            infixString = sc.nextLine();    // read next line of input file
            converter.convertToPostfix(infixString);
            String postfixString = converter.getPostfixString();
            int ans = evaluator.evaluate(postfixString);
            String outString = infixString + " converts to "+
               postfixString + " evaluates to " + ans;
            ps.println(outString);          // print String to output file
            System.out.println(outString);  // print String to screen
         }
      } catch (IOException io) {
         System.out.println(io);
      } catch (InvalidCharacterException e) {
         System.out.println(e);
      } finally {                           // executed if any catch blocks
         System.exit(1);                    // are executed
      }
   }

Command line parameters, File creation, and Sample Output

Important Question: How will your program know which file to read from and write to?

Answer: The code given in the main() method (above) receives the input and output file names from args[0] and args[1], so you need to pass this information in as command line parameters when your program executes.

The first filename (a String) will be saved in args[0] and the second in args[1], respectively--each time you execute your program. You will need to run the Calculator program in the Interactions Pane of DrJava (or at the command line prompt) as follows:

              java Calculator infix.txt output.txt

Create your input file:
Your program will read infix expressions to be converted and evaluated. Create a file named infix.txt, and place it in your A7 directory. Here are two infix expressions, one per line, to get you started:

(3+2)*(4+3*5)+2
((3*2+4/2)*(2+3*5+2))

Put the above lines into your input file, and add at least 5 more tests of your own. For example, you can try some of the infix expressions from problem 14 on page 373 of our textbook. Be sure to add an invalid infix expression, to test whether your code throws an exception, as it should; but put the invalid expression on the last line of your input file--or else the remaining tests won't run.

Sample output:
Here is the sample output when the input file contains the two expressions shown above:

reading
(3+2)*(4+3*5)+2 converts to 32+435*+*2+ evaluates to 97
reading
((3*2+4/2)*(2+3*5+2)) converts to 32*42/+235*+2+* evaluates to 152

The results will also be written to file output.txt, in the same directory as the input file. 

PostfixEvaluator

The PostfixEvaluator class will consist of the following methods and data:

//instance variables
private String postfixString;

//public methods:

/**
 * Uses an Integer stack and applies these 2 rules to
 * evaluate the given postfixString:
 *   if character is an operand, convert to an int and push on stack
 *   else if character is an operator, pop the top 2 items on the stack,
 *       perform the indicated operation (preserving the correct ordering
 *       of the two operands) and push the result on stack
 * Note: character digits in the string must be converted to ints before
 * performing arithmetic operations.
 */
public int evaluate(String postfixString)

/**
 * Getter method for field postfixString.
 */
public String getPostfixString( )

 
The evaluate() method uses these private methods:

/**
 * Returns true if ch is +, -, * , or /
 */
 private boolean isOperator(char ch)
                        
/**
 * Returns true if ch is a digit (0-9)
 */
private boolean isOperand(char ch)
                 
/**
 * Performs the operation on the two integers indicated by
 * the given character parameter 
 */
private int performOp(char op, int val1, int val2)

Note: The comments above are given only as a guide to help you in solving the problem. If you deviate significantly from the suggested class organization, indicate your plan in the header comments on the classes. You should insert method headers and other comments to describe the methods completely. A description of this class is shown in Figure 2, below.

In method   evaluate() you should create an instance of a Stack<Integer>. The characters are read from the given postfixString as type char, but the operands must be converted to ints before they are pushed onto the stack.

Be careful when you implement method  performOp(). The operands will be removed from the stack in the reverse order in which they were placed, a situation that matters when you are doing a division or subtraction operation.

InfixToPostfixConverter

The InfixToPostfixConverter class will consist of the following methods and instance variables:

//instance variables
private String postfixString, infixString;

// Public methods:

/**
 * Uses Stack<Character> and applies the conversion rules shown below
 * in Figure 3
 * to convert given infixString to equivalent postfix expression. 
 * Effect: upon return, infixString and postfixString fields contain 
 * corresponding expressions.
 */
public void convertToPostfix(String infixString)
    throws InvalidCharacterException

/** returns String field postfixString
 *
 */
public String getPostfixString( )
 
// Private methods:

/**
 * returns true if ch is +, -, * , or /
 */
 private boolean isOperator(char ch)
                        
/**
 * returns true if ch is a digit
 */
private boolean isOperand(char ch)

/**
 * returns true if ch is '('
 */
 private boolean isLeftParen(char ch)

/**
 * returns true if ch is ')'
 */
private boolean isRightParen(char ch)

/**
 * returns 1 if given ch is + or - operator
 * returns 2 if given ch is * or / operator 
 * otherwise throws an exception
 */
private int precedence (char ch) throws InvalidCharacterException
                

In the convertToPostfix() method you should create an instance of a  Stack<Character> object and initialize an empty String or StringBuffer object to hold the postfix expression. The StringBuffer class is defined in java.lang and is a "mutable" String class. A mutable object allows changes to its state. For example, you can append characters to the end of a StringBuffer object using a method called append that does not require you to write over the top of the original object or to a new object, as you would have to do when concatenating new characters onto a String object. Look up the StringBuffer class in the Java API to find more methods that are exported for this class. To convert a StringBuffer object to a String, you can use its substring method, starting from position 0. If you choose not to use a StringBuffer, you can just concatenate characters onto the String postfix expression.
 
You should iterate through the given infixString character by character, to determine what kind of character each one is, using the infix-postfix conversion rules given in Figure 3 below to either append the character to the stringBuffer object, push it onto the character stack, or remove characters from the stack and add them to the StringBuffer object. When you have finished traversing the infixString, remove the remaining characters from the character stack and append them to the StringBuffer object. When removing any remaining characters from the stack, you should not encounter a left parenthesis. If you do find an unmatched left parenthesis, or if you encounter a character in the input string that is neither a digit, an operator, nor a parenthesis, throw an InvalidCharacterException. When you have finished performing these steps, field postfixString will contain the postfix version of the converted expression.
 

InvalidCharacterException

Add class InvalidCharacterException to your project. 

public class InvalidCharacterException extends RuntimeException {

  public InvalidCharacterException(String mssg) {
    super(mssg);
  }
}


Some additional information on the process of expression conversion and evaluation, along with examples, is given below in Figures 1 through 4.

Building an arithmetic expression evaluator

Figure 1:  Properties of infix vs postfix expressions

 

Building an arithmetic expression evaluator

Figure 2: Rules for processing postfix strings using a stack

Infix to postfix conversion

Figure 3: Rules for infix to postfix conversion
 

Infix to postfix conversion

Figure 4: Example of infix to postfix conversion

Submitting the project

Once your code is tested and working, submit your project using the following commands in a terminal window (hitting return after each command): 

cd
cd cs125
submit125 A7

You may submit as many times as you wish.  The final submission prior to the deadline will be graded and earlier submissions will be ignored.