CMPU 102 - Assignment 5

CMPU 102 - Assignment 5
Expression Conversion and Evaluation

Assigned: Mon/Tue, Mar 24/25

Due: Mon/Tue, Mar 31/Apr 1

In this Assignment you will build an ExpressionEvaluator in a NetBeans project you will name assign5. Your solution will rely on using an 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 ExpressionEvaluator will consist of the following classes:

public class InfixToPostfixConverter
public class PostfixEvaluator
public class InvalidCharacterException extends Exception, and
public class Main that serves as the driver program for the Expression Evaluator.

Create a new project:
You will run NetBeans and create a new project that you will call assign5. On the top menu bar click on File and select NewProject, then in the next window select General -> Java Application (click on the Next button), and finally in the pop-up window that appears, name your project assign5 and click on Finish.

Add additional classes to your project:
When you open the directory assign5 in your Projects window, you will find a Source Package named assign5 that includes the Main class. Click on this package to highlight it, and then click on File -> NewFile and select Categories: Java Classes; File Types: Java Class and click on the Next button at the bottom of the window. In the next window that appears, you will change the highlighted class name to InfixToPostfixConverter, make sure that the project and package fields both show assign5, and then click on the Finish button at the bottom of this window. The new class is now added to your package. Repeat these directions to create classes PostfixEvaluator and InvalidCharacterException in your assign5 package.

Below is information for implementing each of these classes.

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
// 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

// Helper method used by converter() to initialize field
// to given String infix expression.
private void setInfixString(String infixString)

To implement convertToPostfix() you will create an instance of a Stack<Character> object and initialize an empty string, stringBuffer. You will then iterate through the given infixString, determine what kind of character each one is, then use the infix-postfix conversion rules given below to either append the character to the stringBuffer, push it onto the character stack, or remove characters from the stack and add them to the stringBuffer. When you have finished traversing the infixString,, remove the remaining characters from the character stack and append them to stringBuffer. When removing any remaining characters from the stack, you should not encounter a left parenthesis. If you do find an unmatched left paren, or if you encounter a character in the input string that is not either a digit, an operator, a parenthesis, or a space (if space do nothing), throw an InvalidCharacterException. When you have finished performing these steps, field postfixString will contain the converted expression.

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 the 2 rules listed below to
// evaluate the postfix expression.
// Note: character digits in the string must be converted to ints.
public int evaluate(String postfixString)

// Setter method for field postfixString.
public String getPostfixString( )

The evaluate() method uses these private methods:

// Setter method for field postfixString.
private void setPostfixString(String postfixString)

// 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 passed character --
// throws an exception if ch is not one of the 4 operators
private int performOp(char op, int val1, int val2)

In method evaluate() you will need to 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 type int 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.

InvalidCharacterException

Add class InvalidCharacterException to your project. Replace the autogenerated code with the code given here:

public class InvalidCharacterException extends Exception {

/** Creates a new instance of InvalidCharacterException */
public InvalidCharacterException() {}

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

Main - The Driver Program

Class Main is the ExpressionEvaluator application class--the driver program for this project. It just contains the public static void main() method in which you will create InfixToPostfixConverter and PostfixEvaluator objects. Your main method will do the following:

Scan the input file provided with this lab,
read each infix expression in turn and pass the infix expression to the converter,
get the resulting postfix expression pass it to the evaluator's evaluate method, and
print to the output file: infix string, postfix string, and result for each string read from the input file.

Below is the code for the main() method in class Main. Your will need to add the following import statements to the top of your Main.java file:

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

Replace your Main class's main method with this one:

    public static void main(String[] args) throws Exception {
        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])));
            while (sc.hasNext()) {
                System.out.println("reading");
                String infixString = sc.nextLine();
                converter.convertToPostfix(infixString);
                String postfixString = converter.getPostfixString();
                int ans = evaluator.evaluate(postfixString);
                String outString = infixString + " converts to " +
                                   postfixString + " evaluates to " +
                                   ans;
                ps.println(outString);
                System.out.println(outString);
            }
        } catch (InvalidCharacterException e) {
            System.out.println(e);
            System.exit(1);
        }
    }

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 tell NetBeans to pass this information in as command line parameters when your program executes.

How?: Right-click on the project, go to "Project Properties", click on the "Run" category in the left column, and type the following filenames into the "Arguments:" text box:

infix.text output.txt

The first filename (string) will be saved in args[0] and the second in args[1], respectively--each time you execute your program from NetBeans.

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 NetBeans project directory (the project root: assign5). 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 some more tests of your own--be sure to add an invalid infix expression, to test whether your code throws an exception, as it should. Be sure to 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 from the above two lines:

init:
deps-jar:
compile:
run:
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
BUILD SUCCESSFUL (total time: 0 seconds)

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

To further help you implement the methods of this project, we include (below) some additional information on the process of expression conversion and evaluation, along with examples.

Building an arithmetic expression evaluator

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 cs102
submit102 assign5

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