implement the following methods in an infixExpression class where a program allows the user to type an infix expression. Check that the expression is valid. Then, if it is valid, give the user the equivalent postfix expression, and evaluate the expression.

public InfixExpression(String): This should construct a new InfixExpression object, but will store it as a cleaned up expression. It should make use of the private clean() method to do the cleaning. The constructor should throw an IllegalArgumentException if the String parameter is not valid, calling on the isValid() method for help.

private boolean isBalanced() This private method should return true if the infix expression has balanced parentheses, and false otherwise. It does not check for any other kinds of invalid expressions. So, for example, isBalanced() should return true for the invalid infix expression "( 3 ( ( * * 4 ) 8 ) 7 7 ) 6" because the parentheses are balanced, even though other things are a mess. Use the algorithm described in chapter 5 for checking balanced parentheses. This algorithm should use an instance of your LinkedStack class.

private boolean isValid() This private method should return true if the infix expression is valid in all respects, and false otherwise. For example, isValid() should return false for the infix expression "( 3 ( ( * * 4 ) 8 ) 7 7 ) 6", even though the parentheses are balanced. isValid() should check all of the following:

Whether the expression contains illegal characters (the only valid characters are the digits 0 through 9, the 6 operators and parentheses symbols + - * / % ^ ( ), and spaces.

Whether the parentheses are valid (by calling on isBalanced())

Whether there is an improper order of operators and operands. Observe that each

operator must have an operand before it and after it (an operand can be a number, or an expression in parentheses). For example, the following are NOT valid infix expressions:

"*34"

"3 4 +"

"+"

"3 (4 + 5)" // note that this is implied multiplication...something we will consider

NOT valid

"3**4"

"410"

Note that these ARE valid infix expressions:

"3"

"3 * (5)"

"(4 + 9)"

"((4 + 9))"

private void clean() cleans the expression, cleaning up the provided string by putting a single space between adjacent tokens, and no leading or trailing spaces. So, for example, if the parameter is " 3+4* 83 / 6 ", it should be stored as "3 + 4 * 83 / 6". The only reason this method exists is to help the constructor. That's why it is private. One fairly simple approach to this could be to use the replace() method of the String class to insert spaces where needed, and to convert multiple spaces into single spaces.

public String getPostfixExpression() This method should return the postfix expression that corresponds to the given infix expression. For example, if the infix expression is "3 + 4" then getPostFixExpression() should return "3 4 +"

The operands (numbers) will all be non-negative integer values.

Valid operators are + - * / % ^ (the % is the modulus operator, and has the same level of

precedence as * and /). Parentheses may appear in the expression. This method should assume that the infix expression is valid because the constructor is supposed to be throwing an exception if it is not.

The method should use the algorithm described in section 5.16, along with your LinkedStack class, to compute the postfix expression. The postfix expression should be returned with a single space separating each operand or operator from each adjacent operand or operator, and with no leading or trailing spaces.Note that the algorithm

described in 5.16 assumes operands are single letter variables. For us, our operands will be non-negative integer values that could contain multiple digits (such as 47 or 0 or 999). You will need to modify the algorithm to accommodate for this.

public int evaluatePostfix() This method should evaluate the infix expression, returning the integer result of the calculation. For example, if the infix expression is "13 + 4" then evaluatePostfix() should return 17.

All calculations should be integer calculations. So, for example, the value of the infix expression "7 / 2" should be 3, and not 3.5.

The method should use the algorithm described in section 5.18, along with your LinkedStack class, first using the getPostfixExpression and then evaluating that postfix expression.

Do not do anything special to handle dividing by 0 or computing modulus where the second operand is 0. Just let Java handle that the way that Java likes to handle that.

public int evaluate() This method should evaluate the infix expression directly without converting it to postfix expression, returning the integer result of the calculation. For example, if the infix expression is "13 + 4" then evaluate() should return 17. In this method we are going to convert infix expression directly by using two stacks.

All calculations should be integer calculations. So, for example, the value of the infix expression "7 / 2" should be 3, and not 3.5.

The method should use the algorithm described in section 5.21, along with your LinkedStack class, using two stacks (an operator stack and a value stack) to evaluate infix expression.

Do not do anything special to handle dividing by 0 or computing modulus where the second operand is 0. Just let Java handle that the way that Java likes to handle that.

import java.util.EmptyStackException;

public class LinkedStack implements StackInterface {

private Node topNode; // References the first node in the chain

public LinkedStack() {

topNode = null;

}

@Override

public void push(T newEntry) {

Node newNode = new Node(newEntry);

newNode.next = topNode;

topNode = newNode;

}

@Override

public T pop() {

if(isEmpty()) {

throw new EmptyStackException();

} else {

T result = topNode.data;

topNode = topNode.next;

return result;

}

}

@Override

public T peek() {

if(isEmpty()) {

throw new EmptyStackException();

} else {

return topNode.data;

}

}

@Override

public boolean isEmpty() {

return topNode == null;

}

@Override

public void clear() {

topNode = null;

}

private class Node {

T data; // stores data

Node next; //references the next node

public Node() {

next = null;

}

public Node(T value) {

data = value;

}

}

}