Lab 3 (100 pts)
Due Monday, October 14 at 11:59pm on Canvas

Pair Programming Required (or No Credit)

  • Both partners fill in, sign and date the pair programming contract and BOTH partners submit this file.
  • Only one partner submits the lab assignment on Canvas. Please make sure both your names are on ALL the files.
  • Both partners follow the rules for pair programming.

Part 1: Implementing Your Stack and Queue (65 pts)
  • Begin by implementing the Stack and Queue classes as defined in the lesson notes
  • For the Queue class instructions, see Queue Lesson (Lesson 5)
  • For the Stack class instructions, see Stack Lesson (Lesson 6)
  • Note that you must implement all methods whose signatures are provided. No credit for writing any additional methods for these two classes or for altering the class definitions or method signatures, in any way, aside from implementing the required methods
  • Make sure to test all of your methods to ensure that they are working properly in separate test files, named QueueTest.java and StackTest.java (where you should call each method at least two times inside of main as soon as you write it).
  • When you have finished writing the classes, test your methods further by writing JUnit test classes (3 assertEquals statement per class) for each of the following methods:
    • Queue Class:
      • enqueue
      • dequeue
      • getFront
      • getLength
      • isEmpty
      • equals
      • copy constructor
    • Stack Class:
      • push
      • pop
      • peek
      • getLength
      • isEmpty
      • equals
      • copy constructor
  • Once you are satisfied that your methods are working properly (passing all JUnit tests and the tests you wrote in QueueTest.java and StackTest.java), move on to part 2 below.

Part 2: Polish Calculator (33 pts)

  • Using one or more Stacks (Stack required, optional to use a Queue, in addition), create a calculator program that reads in user input provided in Polish Notation.
  • In Polish notation, the mathematical operators are always placed on the left of the operands (the numbers).
  • This form of notation eliminates the need to use parenthesis to indicate order of operations.
  • Some calculators are programmed this way (though it is rare) or have a Polish notation setting.
  • We are more familiar with infix notation (the way most calculators are programmed.)
  • For example, the following equation, written in both infix and Polish notation

            ((5 + 3) * 4) / 7 //infix notation

     / * + 5 3 4 7 //Polish notation

  • For more information on Polish Notation, read the article here
  • You can also watch this video here


Assumptions

  • For this assignment, you may assume that the user is entering each symbol and number followed by a blank space.
  • For example, assume the user will enter  * 3 + 4 5 rather than *3+45
  • Also, you can assume that the user will only enter integer values (no floating point values).
  • The output can be given as an integer value as well (see below example output).


Hints

  • It is recommend, though not required, that you make use of the following:
    • The static Integer method parseInt to convert Strings to Integers.
    • An is_numeric method (write your own using Unicode)
    • The Scanner constructor that takes in a String parameter, and the hasNext method
  • If you are not familiar with the above, you will be expected to research them for this assignment

Example Output (User Input with Vary):


Welcome!


Please enter an equation in Polish Notation or "q" to quit: * 3 + 4 5
The answer is: 27

Please enter an equation in Polish Notation or "q" to quit: - * - 9 2 3 4
The answer is: 17

Please enter an equation in Polish Notation or "q" to quit: / * + 5 3 4 7
The answer is: 4

Please enter an equation in Polish Notation or "q" to quit: + 13 14
The answer is: 27


Please enter an equation in Polish Notation or "q" to quit: Q


Goodbye!


Specifications for Submission:

  • No credit if you do not complete this assignment using pair programming and following the rules specified in the pair programming contract.
  • No credit if you alter the class or method definitions of the Queue, or Stack or the Node class from the starter code provided in the lesson notes.
  • No credit if you add additional Queue or Stack methods aside from what is provided in the starter code for this lab.
  • No credit on part 2 if you do not implement your solution using your own Stack.java and/or Queue.java class
  • Please submit each file separately (no zip files or other compressed file type -5 pts).
  • Please remove all package statements before submitting (-5 pts).


What to Submit:

  • 2.5 points per correct Queue and Stack method
  • 8 points for the QueueTest.java and StackTest.java files where each method is called at least twice.
  • 14 points for the required 14 JUnit test files (assertEquals called three times per class in a way that tests the method in question).
  • 33 points for a fully functional Polish.java class that works identically to what is shown above in the example output.

Part 3: Palindrome Tester (18 pts)

  • This is a common interview question!
  • Using a Stack and a Queue, determine whether a String is a palindrome (a word spelled the same both forwards and backwards).
  • Create a new text file and save it in the same Lab3 folder along with your Queue.java and Stack.java classes.
  • Copy and paste the following contents into the text file:
A man, a plan, a canal, Panama.
Do geese see God?
Never odd. Even.
Never odd or even.
Eye
Ear
Able was I ere I saw Elba!
Was it Eliot's toilet I saw?
Race cars
Dammit, I’m mad!
On a clover, if alive, erupts a vast, pure evil; a fire volcano.
Nurses run.
Madame, not one man is selfless; I name not one, madame.
Madame, not one man is selfless; I name not one, madam.

  • Another example input file might contain the following:
Don't nod.
Didn't nod.
I did, did I?
My gym
Red rum, sir, is murder
Step on no pets
Step on no poets.
Top spot
Was it a cat I saw?
Eva, can't see bees in a cave?
Eva, can I see bees in a cave?
No lemon, no melon

  • Next, create a new Java class called PalindromeTest.java in the Lab 3 folder.
  • Copy and paste the below starter code into this file:
/**
 * PalindromeTest.java
 * @author
 * @author
 */

import java.io.IOException;
import java.io.File;
import java.util.Scanner;

public class PalindromeTest { 

    private Queue<Character> Q = new Queue<Character>();
    private Stack<Character> S = new Stack<Character>();

    public static void main(String[] args) throws IOException {
        System.out.println("Welcome!\n\nEnter the name of a file: ");         
    }//end of main

}

  • Complete the program to test each phrase in the input file see if it is a palindrome.
  • For credit, you must use only the given Queue and Stack of Characters to solve this problem.
  • You are not allowed to use any additional structures, including any additional Queue(s) or Stack(s).
  • In other words, you must use only 1 Stack and 1 Queue in your solution to this problem in order to receive credit for this assignment - and this Stack and Queue must store Characters.
  • Print out your results to the console, as shown below in the next section.
    • Indicate in parenthesis next to each phrase whether if it is a palindrome as shown below
    • Also you will be required to do some error checking to determine if the user entered a valid file name. (See sample output below)


Your Program Should Give Indentical Output to the Following for Example 1:


Welcome!

Enter the name of a file: pal.txt
Sorry, but I cannot find a file with that name!

Enter the name of a file: pal1.txt
Sorry, but I cannot find a file with that name!

Enter the name of a file: palindrome1.txt

Labeled Data:

A man, a plan, a canal, Panama. (palindrome)
Do geese see God? (palindrome)
Never odd. Even.
Never odd or even. (palindrome)
Eye (palindrome)
Ear
Able was I ere I saw Elba! (palindrome)
Was it Eliot's toilet I saw? (palindrome)
Race cars
Dammit, I’m mad! (palindrome)
On a clover, if alive, erupts a vast, pure evil; a fire volcano. (palindrome)
Nurses run. (palindrome)
Madame, not one man is selfless; I name not one, madame.
Madame, not one man is selfless; I name not one, madam. (palindrome)


Your Program Should Give Indentical Output to the Following for Example 2:


Welcome!


Enter the name of a file: palindrome1.txt

Labeled Data:

Don't nod. (palindrome)
Didn't nod.
I did, did I? (palindrome)
My gym (palindrome)
Red rum, sir, is murder (palindrome)
Step on no pets (palindrome)
Step on no poets.
Top spot (palindrome)
Was it a cat I saw? (palindrome)
Eva, can't see bees in a cave?
Eva, can I see bees in a cave? (palindrome)
No lemon, no melon (palindrome)