You are to write a generic class LinkedDeque which uses a linked-list structure to support seven methods: add, remove, push, pop, peek, isEmpty, and size.

After writing and testing this class, you will then write a main program that uses your deque as a stack in order to evaluate mathematical expressions written in postfix notation.

LinkedDeque

Write a generic class called LinkedDeque Your deque should support the following public methods.

public void push(E x) // Adds x to the front of the deque public E pop() // Removes and returns the front of the deque public void add(E x) // Adds x to the back of the deque public E remove() // Removes and returns the front of the deque public E peek() // Returns the front of the deque without removing it public boolean isEmpty() // Returns true if the deque has no elements public int size() // Returns the number of elements in the deque 

If the client attempts to pop, remove or peek an empty list, your method should throw a NoSuchElementException. Some collection classes do not allow null to be added or pushed, but your LinkedDeque should allow this (ie, d.pop() should return null after d.push(null)).

You may find it useful to write a toString method to help with your debugging, this is allowed, but is not a required element of your class.

ListNode

Use the following class to implement your list's nodes. When testing your LinkedDeque, I will copy this file into your DBInbox folder, so you should not submit it yourself.

public class ListNode { public E data; public ListNode next; public ListNode(E data, ListNode next) { this.data = data; this.next = next; } } 

PostfixEvalMain

Write a main program that uses your LinkedDeque as a stack of integers to evaluate numeric postfix expressions. Recall that the algorithm for this goes like:

while tokens remain get next token if token is an integer push it on the stack else \\ token is an operation pop two integers from the stack combine integers with operation push result stack should contain result 

Your program should repeatedly prompt the user for an expression and print the result. If an input is not a legal postfix expression, "Error" should be printed. This should continue until the word "exit" is entered by the user. The only operators you should support are +, *, /, -. To make things simpler, every pair of tokens will have one or more whitespace characters between them (spaces and/or tabs). For example:

Welcome to Postfix Evaluator 2000! > 2 2 > 22 -3 + 19 > 2 3 4 + * 14 > 2 3 4 +* Error > exit the program Error > exit Goodbye!