package unl.cse.stacks; import java.util.Arrays; import java.util.HashSet; impor

Question

package unl.cse.stacks;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class PostfixEvaluator {

   private static final Set OPERATORS = new HashSet(Arrays.asList("+", "-", "*", "/"));
   private final Stack stack;
  
/**
* Constructor
*/
public PostfixEvaluator() {
this.stack = new Stack();
}

private boolean isOperator(String s){
   return OPERATORS.contains(s);
}
  
private String evaluate(String a, String b, String op) {
   Double d1 = Double.parseDouble(a);
   Double d2 = Double.parseDouble(b);
   if(op.equals("+"))
       return new Double(d1+d2).toString();
   else if(op.equals("-"))
       return new Double(d1-d2).toString();
   else if(op.equals("*"))
       return new Double(d1*d2).toString();
   else if(op.equals("/"))
       return new Double(d1/d2).toString();
   else
       throw new IllegalStateException("Unrecognized operator: "+op);
}

/**
* Evaluates the given arithmetic expression in postfix format
* change this method
* @param expression
* @return
*/
private double evaluateExpression(String expression) {

   String values[] = expression.split("\s+");
   for(String v : values) {
       /*
       * TODO: implement this method
       * Hint:
       * If v is an operator:
       * pop b, a off the stack and call this.evaluate
       * push the result back onto the top of the stack
       * Else
       * push the operand (number) onto the stack
       */
   }
   //At this point, the final result should be on the top of the stack,
   //we pop it off, parse it and return the result
   Double d = Double.parseDouble(this.stack.pop());
return d;
}

/**
*
* @param args
*/
public static void main(String[] args) {

PostfixEvaluator postfixEvaluator = new PostfixEvaluator();
System.out.print("Please enter the Arithmatic Expression (Postfix form) to evaluate: ");
Scanner myScanner = new Scanner(System.in);
String expression = myScanner.nextLine();
System.out.println(expression);
System.out.println("Result: " + postfixEvaluator.evaluateExpression(expression));
}
}

------------------------------------------------------------------------

package unl.cse.stacks;

import unl.cse.linked_list.LinkedList;

public class Stack<T> {

   private final LinkedList<T> list = new LinkedList<T>();
  
   public T pop() {
       //TODO: implement this method
       return null;
   }
  
   public void push(T item) {
       //TODO: implement this method
   }

   public int size() {
       //TODO: implement this method
       return -1;
   }
  
   public boolean isEmpty() {
       //TODO: implement this method
       return false;
   }
  
}

-------------------------------------------------------------------

package unl.cse.linked_list;

import java.util.Iterator;

public class LinkedList<T> implements Iterable<T> {

   private Node<T> head = null;
   private Node<T> tail = null;
  
   public void addElementToHead(T item) {
       if(item == null)
           throw new IllegalArgumentException("This LinkedList impelmentation does not allow null elements");
       Node<T> newHead = new Node<T>(item);
       if(this.tail == null) {
           this.head = newHead;
           this.tail = newHead;
       } else {
           newHead.setNext(this.head);
           this.head.setPrevious(newHead);
           this.head = newHead;
       }
   }
  
   public T removeElementFromHead() {
       T item = null;
       if(this.size() == 0) {
           throw new IllegalStateException("Cannot remove from an empty list");
       } else if(this.size() == 1) {
           item = this.head.getItem();
           this.head = null;
           this.tail = null;
       } else {
           item = this.head.getItem();
           this.head = this.head.getNext();
           this.head.setPrevious(null);
       }
       return item;
   }
  
   /**
   * Returns the element at the head of this list, but does not remove it.
   * @return
   */
   public T getElementFromHead() {
       if(this.size() == 0) {
           throw new IllegalStateException("Cannot retrieve from an empty list");
       } else {
           return this.head.getItem();
       }
   }
  
   public void addElementToTail(T item) {
       if(item == null)
           throw new IllegalArgumentException("This LinkedList impelmentation does not allow null elements");
       Node<T> newTail = new Node<T>(item);
       if(this.tail == null) {
           this.tail = newTail;
           this.head = newTail;
       } else {
           newTail.setPrevious(this.tail);
           this.tail.setNext(newTail);
           this.tail = newTail;
       }
   }
  
   public T removeElementFromTail() {
       T item = null;
       if(this.size() == 0) {
           throw new IllegalStateException("Cannot remove from an empty list");
       } else if(this.size() == 1) {
           item = this.tail.getItem();
           this.head = null;
           this.tail = null;
       } else {
           item = this.tail.getItem();
           this.tail = this.tail.getPrevious();
           this.tail.setNext(null);
       }
       return item;
   }

   /**
   * Returns the element at the tail of this list, but does not remove it.
   * @return
   */
   public T getElementFromTail() {
       if(this.size() == 0) {
           throw new IllegalStateException("Cannot retrieve from an empty list");
       } else {
           return this.tail.getItem();
       }
   }

   public int size() {
       int count = 0;
       for(T item : this) {
           count++;
       }
       return count;
   }
  
   public boolean isEmpty() {
       return (head == null);
   }
  
   @Override
   public Iterator<T> iterator() {
       return new Iterator<T>() {
           Node<T> curr = head;
           @Override
           public boolean hasNext() {
               if(curr == null)
                   return false;
               else
                   return true;
           }
           @Override
           public T next() {
               T item = curr.getItem();
               curr = curr.getNext();
               return item;
           }

           @Override
           public void remove() {
               throw new UnsupportedOperationException("not implemented");
           }};
   }

   @Override
   public String toString() {
       if(this.head == null) {
           return "[empty]";
       }
       StringBuilder sb = new StringBuilder();
       sb.append("[");
       Node<T> curr = head;
       while(curr != null) {
           sb.append(curr.getItem());
           if(curr.getNext() != null)
               sb.append(", ");
           curr = curr.getNext();
       }
       sb.append("]");
       return sb.toString();
   }

   public static void main(String args[]) {
       LinkedList<Integer> llist = new LinkedList<Integer>();
       llist.addElementToHead(10);
       llist.addElementToHead(20);
       llist.addElementToTail(-10);
       llist.addElementToTail(-20);
       System.out.println(llist);
       System.out.println(llist.removeElementFromHead());
       System.out.println(llist.removeElementFromTail());
       System.out.println(llist);
       llist.addElementToTail(-50);
       llist.addElementToTail(-60);
       System.out.println(llist);
       System.out.println(llist.isEmpty());
       System.out.println(llist.removeElementFromTail());
       System.out.println(llist.removeElementFromTail());
       System.out.println(llist.removeElementFromTail());
       System.out.println(llist.removeElementFromTail());
       System.out.println(llist.isEmpty());
       llist.addElementToTail(-50);
       llist.addElementToTail(-60);
       System.out.println(llist);
   }

}

Postfix notation (also known as Reverse Polish Notation) is a parenthesis -free way of writing arithmetic expressions where one places the operator symbol after its two operands. For example, the expression (3 + 2) would be written 3 2 +; the result of this value multiplied by 4 could be written 3 2 + 4 *. A full example: the expression (3 + 2) 4) / (5 - 1) is written as: 3 2 + 4 * 5 1 - /. Manually computing: The advantage of postfix notation is that no precedence rules are necessary as the order of operation is completely unambiguous. Many calculators, mathematical tools, and other systems utilize this notation. Evaluation of postfix expressions can be done using a Stack data structure. Recall that a Stack is a LIFO (Last -In First -Out) data structure. Stacks, like many data structures, can be implemented in many different ways. In this lab, our implementation will utilize a linked list data structure. This data structure has been completely implemented for you. Most of the code needed to read -in a postfix expression and evaluate it has also been provided to you. You will complete the application by implementing the Stack data structure and use it in the postfix evaluation program.

Explanation / Answer

Here you go :)

comment if you have any doubts

//PostfixEvaluator clas

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class PostfixEvaluator {

   private static final Set OPERATORS = new HashSet(Arrays.asList("+", "-",
           "*", "/"));
   private final Stack stack;

   /**
   * Constructor
   */
   public PostfixEvaluator() {
       this.stack = new Stack();
   }

   private boolean isOperator(String s) {
       return OPERATORS.contains(s);
   }

   private String evaluate(String a, String b, String op) {
       Double d1 = Double.parseDouble(a);
       Double d2 = Double.parseDouble(b);
       if (op.equals("+"))
           return new Double(d1 + d2).toString();
       else if (op.equals("-"))
           return new Double(d1 - d2).toString();
       else if (op.equals("*"))
           return new Double(d1 * d2).toString();
       else if (op.equals("/"))
           return new Double(d1 / d2).toString();
       else
           throw new IllegalStateException("Unrecognized operator: " + op);
   }

   /**
   * Evaluates the given arithmetic expression in postfix format change this
   * method
   *
   * @param expression
   * @return
   */
   private double evaluateExpression(String expression) {

       String values[] = expression.split("\s+");
       for (String v : values) {
           /*
           * TODO: implement this method Hint: If v is an operator: pop b, a
           * off the stack and call this.evaluate push the result back onto
           * the top of the stack Else push the operand (number) onto the
           * stack
           */
          
           if(isOperator(v))
           {
               String a=(String)this.stack.pop();
               String b=(String) this.stack.pop();
               this.stack.push((String)this.evaluate(b,a, v));
           }
           else this.stack.push(v);
       }
       // At this point, the final result should be on the top of the stack,
       // we pop it off, parse it and return the result
       Double d = Double.parseDouble((String) this.stack.pop());
       return d;
   }

   /**
   *
   * @param args
   */
   public static void main(String[] args) {

       PostfixEvaluator postfixEvaluator = new PostfixEvaluator();
       System.out
               .print("Please enter the Arithmatic Expression (Postfix form) to evaluate: ");
       Scanner myScanner = new Scanner(System.in);
       String expression = myScanner.nextLine();
       System.out.println(expression);
       System.out.println("Result: "
               + postfixEvaluator.evaluateExpression(expression));
   }
}

//########################################################################

//Stack class

public class Stack<T> {

   private final LinkedList<T> list = new LinkedList<T>();

   public T pop() {

       T t = list.getElementFromHead();
       list.removeElementFromHead();
       return t;
   }

   public void push(T item) {
       list.addElementToHead(item);
   }

   public int size() {

       return list.size();
   }

   public boolean isEmpty() {

       return list.isEmpty();
   }

}

//#######################################################################

//LinkedList class

import java.util.Iterator;

public class LinkedList<T> implements Iterable<T> {

   private Node<T> head = null;
   private Node<T> tail = null;

   public void addElementToHead(T item) {
       if (item == null)
           throw new IllegalArgumentException(
                   "This LinkedList impelmentation does not allow null elements");
       Node<T> newHead = new Node<T>(item);
       if (this.tail == null) {
           this.head = newHead;
           this.tail = newHead;
       } else {
           newHead.setNext(this.head);
           this.head.setPrevious(newHead);
           this.head = newHead;
       }
   }

   public T removeElementFromHead() {
       T item = null;
       if (this.size() == 0) {
           throw new IllegalStateException("Cannot remove from an empty list");
       } else if (this.size() == 1) {
           item = this.head.getItem();
           this.head = null;
           this.tail = null;
       } else {
           item = this.head.getItem();
           this.head = this.head.getNext();
           this.head.setPrevious(null);
       }
       return item;
   }

   /**
   * Returns the element at the head of this list, but does not remove it.
   *
   * @return
   */
   public T getElementFromHead() {
       if (this.size() == 0) {
           throw new IllegalStateException(
                   "Cannot retrieve from an empty list");
       } else {
           return this.head.getItem();
       }
   }

   public void addElementToTail(T item) {
       if (item == null)
           throw new IllegalArgumentException(
                   "This LinkedList impelmentation does not allow null elements");
       Node<T> newTail = new Node<T>(item);
       if (this.tail == null) {
           this.tail = newTail;
           this.head = newTail;
       } else {
           newTail.setPrevious(this.tail);
           this.tail.setNext(newTail);
           this.tail = newTail;
       }
   }

   public T removeElementFromTail() {
       T item = null;
       if (this.size() == 0) {
           throw new IllegalStateException("Cannot remove from an empty list");
       } else if (this.size() == 1) {
           item = this.tail.getItem();
           this.head = null;
           this.tail = null;
       } else {
           item = this.tail.getItem();
           this.tail = this.tail.getPrevious();
           this.tail.setNext(null);
       }
       return item;
   }

   /**
   * Returns the element at the tail of this list, but does not remove it.
   *
   * @return
   */
   public T getElementFromTail() {
       if (this.size() == 0) {
           throw new IllegalStateException(
                   "Cannot retrieve from an empty list");
       } else {
           return this.tail.getItem();
       }
   }

   public int size() {
       int count = 0;
       for (T item : this) {
           count++;
       }
       return count;
   }

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

   @Override
   public Iterator<T> iterator() {
       return new Iterator<T>() {
           Node<T> curr = head;

           @Override
           public boolean hasNext() {
               if (curr == null)
                   return false;
               else
                   return true;
           }

           @Override
           public T next() {
               T item = curr.getItem();
               curr = curr.getNext();
               return item;
           }

           @Override
           public void remove() {
               throw new UnsupportedOperationException("not implemented");
           }
       };
   }

   @Override
   public String toString() {
       if (this.head == null) {
           return "[empty]";
       }
       StringBuilder sb = new StringBuilder();
       sb.append("[");
       Node<T> curr = head;
       while (curr != null) {
           sb.append(curr.getItem());
           if (curr.getNext() != null)
               sb.append(", ");
           curr = curr.getNext();
       }
       sb.append("]");
       return sb.toString();
   }

   public static void main(String args[]) {
       LinkedList<Integer> llist = new LinkedList<Integer>();
       llist.addElementToHead(10);
       llist.addElementToHead(20);
       llist.addElementToTail(-10);
       llist.addElementToTail(-20);
       System.out.println(llist);
       System.out.println(llist.removeElementFromHead());
       System.out.println(llist.removeElementFromTail());
       System.out.println(llist);
       llist.addElementToTail(-50);
       llist.addElementToTail(-60);
       System.out.println(llist);
       System.out.println(llist.isEmpty());
       System.out.println(llist.removeElementFromTail());
       System.out.println(llist.removeElementFromTail());
       System.out.println(llist.removeElementFromTail());
       System.out.println(llist.removeElementFromTail());
       System.out.println(llist.isEmpty());
       llist.addElementToTail(-50);
       llist.addElementToTail(-60);
       System.out.println(llist);
   }

}

//######################################################################

//Node class

public class Node<T> {

   private final T item;
   private Node<T> prev;
   private Node<T> next;

   public Node(T item) {
       this.item = item;
       next = null;
   }

   public T getItem() {
       return this.item;
   }

   public void setNext(Node<T> next) {
       this.next = next;
   }

   public void setPrevious(Node<T> prev) {
       this.prev = prev;
   }

   public Node<T> getNext() {
       return this.next;
   }

   public Node<T> getPrevious() {
       return this.prev;
   }

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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