Java Foundations

Objectives

Create a LinkedStack implementation.

Create a postfix calculator for evaluating postfix arithmetic expressions.

Tasks

1. Create a class called LinkedStack which implements the StackADT interface.

2. Create a class called PostfixCalculator containing a single public method called run() which will take no parameters. The class will have an instance variable of type LinkedStack.

3. The run() method will implement a text interface that looks like the example 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 and 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. As indicated below, you should print NaN (the Double.NaN constant), if the input is numerically invalid in any way.

:::> 3 4 + 7.0 :::> 3 3.0 :::> -3 44 + 41.0 :::> 3 4 + 0 / Invalid input: divided by zero NaN :::> 7 8 2 - * 5 3 + 6 / + 4 * 173.33333333333334 :::> :::> :::> 3 4 Invalid input: too many operands NaN :::> 3 4 + * Invalid input: not enough operands NaN :::> @ 2 Invalid input: unrecognized character: @ NaN :::> q Goodbye! 

Evaluate the postfix expression by using the stack instance 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.

PostFixCalculator.java

import java.util.Scanner; public 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; } }

EmptyCollectionException.java

/** * 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."); } } LinkedStack.java

package edu.unca.csci202;

public class LinkedStack implements StackADT { // inner class: linked list node private class Node { private T element; private Node next; }

// data fields private int size; // number of elements stored private Node top; // top of stack // constructor public LinkedStack() { this.size = 0; this.top = null; }

// interface method definitions from StackADT @Override public void push(T element) { // create a new Node Node newMode = new Node(); newNode.element = element; newNode.next = this.top; // update the top to point to new node this.top = newNode; this.size++; }

@Override public T pop() { T grabbedElt = this.peek(); // also does the empty check // remove first element from stack this.top = this.top.next; this.size--; return grabbedElt; }

@Override public T peek() { if (this.isEmpty()) { throw new EmptyCollectionException("LinkedStack"); } return this.top.element; }

@Override public boolean isEmpty() { // TODO Auto-generated method stub return (this.size == 0); }

@Override public int size() { // TODO Auto-generated method stub return this.size; } // toString method @Override public String toString() { String s = ""; s = s + "LinkedStack of size" + this.size() + " containing (top is on left): "; // iterate through the elements and glue them on to string for(Node curr = this.top; curr != null; curr = curr.next) { s = s + curr.element; if(curr.next != null) { s = s + ", "; } else { s = s + "."; } } return s; } // tester main public static void main(String[] args) { StackADT stack = new LinkedStack(); stack.push("hi"); stack.push("woah"); stack.push("yo"); System.out.println(stack); while(!stack.isEmpty()) { System.out.println(stack.pop()); } } } StackADT.java

package edu.unca.csci202;

/** * Defines the interface to a stack collection. * * @author Java Foundations * @version 4.0 */ public interface StackADT { /** * 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 T pop();

/** * 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 T peek();

/** * 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();

}