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

Pair Programming Requirement (-75 pts for Not Pair Programming)

  • 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 and (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 and, move on to part 2 below.

Part 2: Polish Calculator (35 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


  • 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).


  • 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):


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


Specifications for Submission:

  • -75 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.
  • 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 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 and files where each method is called at least twice.
  • 12 points for the required 12 JUnit test files (assertEquals called three times per class in a way that tests the method in question).
  • 35 points for a fully functional class that works identically to what is shown above in the example output.