**The following program code must be done in Java.**

One common way for a compiler for a high-level language to generate machine language instructions to evaluate arithmetic or Boolean expressions, involves a conversion of the expression of the expression from infix to postfix. Typically, the compiler does not require a fully parenthesized expression as input, but instead has a table of priorities which indicate the order in which operators will be applied within a pair of parentheses (the operator with highest priority is evaulated first).

For example, consider a compiler with the following set of priorities:

Operator	Priority
^, ~, unary +, unary -	6
*, /	5
+, -	4
<, <=, =, <>, >, >=	3
and	2
or	1

Then the expression:

A / B ^ C + D * E - A * C

will be evaluated as:

((A / (B ^ C)) + (D * E)) - (A * C)

and its postfix form would be:

A B C ^ / D E * + A C * -

For this lab, you are to design, implement, and test a Java program that reads infix expressions from a file, infix.txt, converts the infix expression to postfix notation, and evaluates the postfix expressions. We make the following simplifying assumptions:

- All opertors and operands are one character long in the original infix expression.

- Allowable operators are +, -, *, / (integer division), ^ (exponentation).

- All operators are left associative.

- There are no unary operators.

- Each exression is contained on its own line within the file.

- Parentheses can of course be used in normal fashion, and blanks should be allowed between symbols. The infix expressions below should be read into your program from a file, infix.txt.

8 + 4 * 2 - 6

7 * 2 - 4 * 3 + 2 * 5

2 * 3 * 4 - 8 + 9 / 3 / 3

5 + 7 * 4 - 6

4 * (3 + 2 * 4) - 7

(5 + 7) / (9 - 5)

3 * (5 * (5 - 2)) - 9

((5 * (4 + 2) - (8 + 8) / 2) - 9) ^ 3

((5 + 5 * (6 - 2) + 4 ^ 2) * 8)

((( 3 ^ 4)))

Be sure that your program outputs the original infix expression, its postfix equivalent, as well as the evaluation of the postfix expression. All output should be sent to a file called csis.txt. The only stack class that should be used in this lab is the ObjectStack class that we developed. You should use at least the following classes and interface in the lab:

Driver, InfixToPostfix, ObjectStac, EvalPostfix, & ObjectStackInterface

The only user-defined static function in the lab should be main(). No floats, doubles, or scientific notation should be used.

For extra credit, your program should also be able to handle these ill-formed expressions below, indicating that such an expression is erroneous, identifying the type of error, and going on to process the next infix expression.

1 + * 2 adjacent operators

1 2 * 3 ^ 4 adjacent operands

( 1 + 2 missing parenthesis

( 1 + 2 ) * 3 ) extra parenthesis

Stack Lab Note 1: Scanner Class

You can use Java's Scanner class to open a file for input.

Required declarations:

import java.io.*;

import java.util.Scanner;

public static void main(String[] args) throws IOException {

To open a file for input and create a Scanner object:

Scanner fileScan = new Scanner(new File("infix.txt"));

To read a lien from the file using the Scanner object:

while (fileScan.hasNext()) {

String buf = fileScan.nextLine();

To close the Scanner object:

fileScan.close();

Stack Lab Note 2: Operator Precedence

The conversion from infix to postfix will require the comparison of operator priorities. Here's a method that will take an operator as input and return its priority:

private int priority(char op) {

switch (op) {

case '^': return 3;

case '*':

case '/': return 2;

case '+':

case '-': return 1:

default : return 0:

}

}

Stack Lab Note 3: Program Documentation

Every class must have a Javadoc class comment.

Every method must have a Javadoc method comment.

Every method parameter must have an @param tag.

Every method with a return statement must have an @return tag.

Generate the HTML Javadoc documentation for your project and be sure to submit the folder that contains the Javadoc documentation in the zip archive when submitting the lab.

Stack Lab Note 4: Interfaces

Each data structure in your project must implement an interface for that data structure. The interface files must be included in the zip archive for your code.

ObjectStack class

// ObjectStack.java

public class ObjectStack { private Object[] item; private int top; public ObjectStack() { item = new Object[1]; top = -1; }

public boolean isEmpty() { return top == -1; }

public boolean isFull() { return top == item.length-1; } public void clear() { item = new Object[1]; top = -1; } public void push(Object o) { if (isFull()) resize(2 * item.length); item[++top] = o; } private void resize(int size) { Object[] temp = new Object[size]; for (int i = 0; i <= top; i++) temp[i] = item[i]; item = temp; } public Object pop() { if (isEmpty()) { System.out.println("Stack Underflow."); System.exit(1); } Object temp = item[top]; item[top--] = null; if (top == item.length/4) resize(item.length/2); return temp; } public Object top() { if (isEmpty()) { System.out.println("Stack Underflow."); System.exit(1); } return item[top]; } }