Java

Objectives 1. Create a LinkedStack implementation. 2. Create a postfix calculator for evaluating postfix arithmetic expressions. Introduction Reverse Polish Notation (RPN), also known as postfix, is a way of writing arithmetic expressions so that the operator follows its operands. For example, if wish to add 3 and 4 , I would write it as 34+. If I wanted to multiply this same expression by 7 , I would write 34+7. The same expression would be written (3+4)7 in standard or infix notation. Converting to postfix from infix gets easier with practice. One way of doing the conversion is to draw the abstract syntax tree for the given expression and then perform a post-order traversal on it. The main thing to remember is to write the operands for the first operation you wish to perform first and then follow them with the operator. Continuing in this fashion, you can build up the postfix expression. For example, take the expression (7(82)+(5+3)/6)4. We start by subtracting 2 from 8:82. We then multiply by 7 , remembering that 7 is the left operand of the multiply: 782. We can now work on the right-hand term: 53+6/. These are combined by an addition giving: 78253+6/+. Finally, we multiply by 4: 78253+6/+4 Postfix expressions can be evaluated efficiently by utilizing a stack and the following algorithm. Start by scanning left-to-right over the input expression, one token at a time. When we see a number, push it onto the stack. When we see an operator, we pop two operands from the stack, apply the operation to them, and push the result back on the stack. When we reach the end of a properly formatted expression, there will be exactly one number left on the stack, which is the final answer. Tasks 1. Create a class called LinkedStack which implements the StackADT interface. 2. Create a class called Postfixcalculator with the main method. The main method will implement a text interface that looks like the examples below. The user will be presented with a prompt: ": : :> ". Then they will type a postfix expression and press enter. The operands and operators should be separated by spaces on the input line. At that point, your calculator will perform the indicated operations to evaluate the expression then print out the result followed by a new prompt. Your program should never crash. Be sure to handle all errors that arise, either by parsing the input yourself or by catching any exceptions thrown. Make sure your calculator handles all these situations properly, including: a correct expression, division by zero, a blank input, too many operands, too few operands, and an unrecognized character. Use the error messages shown in the examples below: :::>34+ 7.0 :::>3 3.0 :::>344+ 41.0 :::>34+0/ Invalid input: divide by zero :::>782-*53+6/+4* 173. 33333333333334 :::> :::> :::>34 Invalid input: too many operands :::>34+* Invalid input: not enough operands :::>@2 Invalid input: unrecognized token: @ :::>q Goodbye! Evaluate the postfix expression by using a LinkedStack variable in the manner discussed in the introduction. I suggest using an if statement that looks at the first character of each token and performs the appropriate operation, i.e. numbers should be pushed onto the stack, arithmetic operations should be performed, the calculator terminated if ' q ' is entered, etc. Your calculator should handle the,+ , , - , and / operators. EmptyCollectionException.java 19 September 2023, 7:41 PM StackADT.java 19 September 2023, 7:41 PM / * Represents the situation in which a collection is empty. * * @author Java Foundations * @version 4.0 */ public class EmptyCollectionException extends RuntimeException \{ /** * Sets up this exception with an appropriate message. * @param collection the name of the collection */ public EmptyCollectionException(String collection) \{ super("The " + collection + " is empty."); \} \} // inner class node private class Node T{ private T element; private Node T next; \} // LinkedStack data fields private int count; // size counter num elements in stack private Node top; // head of the list, top of stack // default constructor makes empty stack // StackADT interface methods @override public void push( T element) \{ Node T newNode = new Node >(); newNode. element = element; newNode. next = this.top; this. top = newNode; this. count++; \} @Override public T pop() \{ T retVal = this. . peek () ; this. top = this.top. next; this. count--; return retVal; \} @override public T peek() \{ if(this.isEmpty ()){ throw new EmptyCollectionException("LinkedStack"); \} return this.top.element; \} @override public boolean isEmpty() \{ return (this.top == null); \} @override public int size() \{ return this.count; \} @Override public String toString() \{ String s= "LinkedStack of size " + this.count + " containing (top on the left)"; Node T current = this. top; while(current != null) \{ s=s+ current.element +" "; current = current. . next; \} return s; \} mport java.util.Scanner; ublic class PostfixCalculator \{ / * Run a post-fix calculator on the console */ private static void run() \{ Scanner scan = new Scanner(System.in); String inputLine = " "; boolean wantToQuit = false; while (!wantToQuit) {// process one expression // getting a non empty input from the user // after that, we have a non-empty string on the input line variables // evaluate the expression and print the result wantToQuit = evalExpression (inputLine); \} // end of user input loop System.out.println("Goodbye!"); \} / * evaluates a post-fix expression * @param inputLine the expression to be evaluated * @return true if the user typed q, otherwise false */ private static boolean evalExpression(String inputLine) \{ if (inputLine. charAt(0)== 'q') {// user wants to quit return true; \} // otherwise evaluate the expression in a loop going through tokens return false; \} * Defines the interface to a stack collection. @author Java Foundations @version 4.0 / blic interface StackADT T>{ / * Adds the specified element to the top of this stack. * @param element element to be pushed onto the stack */ public void push(T element); / * Removes and returns the top element from this stack. * * @return the element removed from the stack * @throws EmptyCollectionException if the stack is empty */ public Tpop(); / * Returns the top element of this stack without removing it from the stack. * * @return the element on top of the stack. It is not removed from the stack * @throws EmptyCollectionException if the stack is empty */ public Tpeek(); / * Returns true if this stack contains no elements. * * @return true if the stack is empty, false if the stack is not empty */ public boolean isEmpty(); / * Returns the number of elements in this stack. * * @return the number of elements in the stack */ public int size()