Create a driver class Main.java that tests the two files LinkedStack.java and Postfix.java (code for both are provided below).

Postfix.java contains the methods convertToPostfix(String infix) and evaluatePostfix(String postfix), which both need to be implemented.

The driver program should be able to pass infix equations to PostFix.convertToPostfix() which should be returned properly converted. You do not need to test to see if an incoming String is a valid infix equation

Please make sure when you are testing your program that you only pass proper postfix equations as arguments. Use the variables a, b, c, d, and/or e.

I have implemented a helper method on Postfix.java that will convert these variables into numbers. You simply need to call getValue(Character c) to retrieve the proper integer value for each variable.

Running the following code in your driver program should print out:

a b c / +

2

String postfix = PostFix.convertToPostfix("a + b / c");

System.out.println(postfix);

System.out.println(PostFix.evaluatePostfix(postfix));

I have also implemented a few other helper methods for you:

getPrecedence(char operator) returns an int indicating the precedence of the operator passed in. The higher the int returned, the higher the order of precedence of the operator.

isVariable(char character) returns true if the incoming character is a variable.

isOperator(char chacter) returns true if the incoming character is an operator.

In your driver class, the following code should print out the value '2'.

LinkedStack.java:

import java.util.EmptyStackException;

public class LinkedStack implements StackInterface { private Node topNode; public LinkedStack() { topNode = null; }

private class Node { private T data; private Node next; private Node(T d, Node n) { data = d; next = n; }

private T getData() { return data; }

private Node getNextNode() { return next; } }

@Override public void push(T newEntry) { topNode = new Node(newEntry, topNode); }

@Override public T pop() { if(isEmpty()) { throw new EmptyStackException(); } T top = topNode.getData(); topNode = topNode.getNextNode(); return top; }

@Override public T peek() { if(isEmpty()) { throw new EmptyStackException(); } return topNode.getData(); }

@Override public boolean isEmpty() { return topNode == null; }

@Override public void clear() { topNode = null; } }

Postfix.java (please add code under "TODO"):

public class Postfix { public static String convertToPostfix(String infix) { StackInterface operatorStack = new LinkedStack();

// use a StringBuilder object rather than a String, since appending is much more efficient. // To add to the StringBuilder object 'postfix': // postfix.append(stringToAppend); StringBuilder postfix = new StringBuilder(); int length = infix.length(); for(int i = 0; i // TODO } else { switch(nextCharacter) { // TODO default: break; } } }

return postfix.toString(); }

public static int evaluatePostfix(String postfix) { // TODO return 0; }

private static int getValue(Character c) { switch(c) { case 'a': return 2; case 'b': return 3; case 'c': return 4; case 'd': return 5; case 'e': return 6; default: return 0; } }

private static int performOperation(int operandOne, int operandTwo, char operator) { // TODO return 0; }

private static int getPrecedence(char operator) { switch (operator) { case '(': case ')': return 0; case '+': case '-': return 1; case '*': case '/': return 2; case '^': return 3; } return -1; }

private static boolean isOperator(char c) { return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^'); }

private static boolean isVariable(Character c) { return Character.isLetter(c); } }

StackInterface.java:

import java.util.EmptyStackException;

public interface StackInterface { /** Adds a new entry to the top of this stack. * @param newEntry An object to be added to the stack. */ void push(T newEntry);

/** Removes and returns this stack's top entry * @return The object at the top of the stack * @throws EmptyStackException if the stack is empty*/ T pop();

/** Retrieves this stack's top entry. * @return The object at the top of the stack. * @throws EmptyStackException if the stack is empty.*/ T peek();

/** Detects whether this stack is empty * @return True if the stack is empty. */ boolean isEmpty();

/** removes all entries from this stack */ void clear(); }

Please provide comments in the code for explanation if possible. Thank you!

Pseudocode for convertToPostfix(String infix):

Pseudocode for evaluatePostfix(String postfix):

Algorithm convertToPostfix(infix) Converts an infix expression to an equivalent postfix expression operatorStack a new empty stack postfix-a new empty string while (infix has characters left to parse) nextCharacter-next nonblank character of infix switch (nextCharacter) case variable: Append nextCharacter to postfix break case 'A: operatorStack.push (nextCharacter) break case '+: case"': casecase/" while CloperatorStack.isEmptyand precedence of nextCharacterprecedence of operatorStack.peek ()) Append operatorStack.peek ) to postfix operatorStack.pop operatorStack.push (nextCharacter) break case'' operatorStack.push (nextCharacter) break case' :11 Stack is not empty if infix expression is valid topOperator-operatorStack.popO while (topOperatorC Append topoperator to postfix topOperator-operatorStack.popO break default: break//Ignore unexpected characters while CloperatorStack.isEmptyO) ack.popCO topOperator-operatorSt Append topOperator to postfix return postfix Algorithm evaluatePostfix(postfix) IEvaluates a postfix expression valueStack a new empty stack while (postfix has characters left to parse) nextCharacter -next nonblank character of postfix switch (nextCharacter) valueStack.push(value of the variable nextCharacter) break case'case':case:case case'A' operandTwo valueStack. pop() operandOne- valueStack.popO result - the result of the operation in nextCharacter and its operands operandOne and operandTwo valueStack.push(result) break default: break// Ignore unexpected characters return valueStack.peek O Algorithm convertToPostfix(infix) Converts an infix expression to an equivalent postfix expression operatorStack a new empty stack postfix-a new empty string while (infix has characters left to parse) nextCharacter-next nonblank character of infix switch (nextCharacter) case variable: Append nextCharacter to postfix break case 'A: operatorStack.push (nextCharacter) break case '+: case"': casecase/" while CloperatorStack.isEmptyand precedence of nextCharacterprecedence of operatorStack.peek ()) Append operatorStack.peek ) to postfix operatorStack.pop operatorStack.push (nextCharacter) break case'' operatorStack.push (nextCharacter) break case' :11 Stack is not empty if infix expression is valid topOperator-operatorStack.popO while (topOperatorC Append topoperator to postfix topOperator-operatorStack.popO break default: break//Ignore unexpected characters while CloperatorStack.isEmptyO) ack.popCO topOperator-operatorSt Append topOperator to postfix return postfix Algorithm evaluatePostfix(postfix) IEvaluates a postfix expression valueStack a new empty stack while (postfix has characters left to parse) nextCharacter -next nonblank character of postfix switch (nextCharacter) valueStack.push(value of the variable nextCharacter) break case'case':case:case case'A' operandTwo valueStack. pop() operandOne- valueStack.popO result - the result of the operation in nextCharacter and its operands operandOne and operandTwo valueStack.push(result) break default: break// Ignore unexpected characters return valueStack.peek O