You are to write a generic class LinkedDeque which uses a linked-list structure

Question

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<E>

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

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<E>

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.

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:

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:

Explanation / Answer

import java.util.*;

class Deque<E> {

    private int size;
    private ListNode first;
    private ListNode last;

    public Deque() {

    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return size;
    }

    public void push(E item) {
        throwIfNull(item);

        ListNode newFirst = new ListNode();
        newFirst.item = item;

        if (first != null) {
            newFirst.next = first;
            first.previous = newFirst;
        }
        first = newFirst;
        if (last == null) last = first;

        size++;
    }

    public E pop() {
        throwIfEmpty();

        ListNode oldFirst = first;
        first = first.next;

        if (first == null)
            last = null;
        else
            first.previous = null;

        size--;

        return oldFirst.item;
    }

    public void add(E item) {
        throwIfNull(item);

        ListNode newLast = new ListNode();
        newLast.item = item;

        if (last != null) {
            newLast.previous = last;
            last.next = newLast;
        }
        last = newLast;
        if (first == null) first = last;

        size++;
    }

    public E remove() {
        throwIfEmpty();

        ListNode oldLast = last;
        last = oldLast.previous;

        if (last == null)
            first = null;
        else
            last.next = null;

        size--;

        return oldLast.item;
    }

    private void throwIfEmpty() {
        if (first == null)
            throw new NoSuchElementException();
    }

    private void throwIfNull(E item) {
        if (item == null)
            throw new NullPointerException();
    }

    private class ListNode {
        E item;
        ListNode next;
        ListNode previous;
    }

}

public class PostEvalDeque
{
   public static void main(String a[])
   {
      Deque list = new Deque();
    
    
      String exp="2 3 4 + *";
      int number1;
        int number2;
        int result=0;

        String[] tokens = exp.split(" ");

            for(int j = 0; j < tokens.length; j++)
            {
                String token = tokens[j];
              
            if (!"+".equals(token) && !"*".equals(token) && !"-".equals(token) && !"/".equals(token))
            {
                list.push(Integer.parseInt(token));
              

             }   else
             {
                String Operator = tokens[j];
                number1 = (int)list.pop();
                number2 = (int)list.pop();
              
                if (Operator.equals("/")){
                    result = number1 / number2;}
                else if(Operator.equals("*")){
                    result = number1 * number2;}
                else if(Operator.equals("+")){
                    result = number1 + number2;}
                else if(Operator.equals("-")){
                    result = number1 - number2;}
                else System.out.println("Illeagal symbol");
              
                list.push(result);
                //System.out.println(result+" Hee ");
            }
              
             
                  
           }

      
        System.out.println("Postfix Evauation = " + result);

   }
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.