CSSE 230
Stacks And Queues Programming Assignment  - 100 Points

Overview and objectives

Stacks and queues are simple, yet very useful data structures. In this assignment, you will:

  1. Implement the Queue ADT using a circular array that grows efficiently.
  2. Analyze four different implementations of the Queue ADT.
  3. Develop practical algorithms that require a stack by creating a tool to evaluate simple mathematical expressions.

Starting code is in the StacksAndQueues project in your pair's repository (see link from schedule page for your team number). Commit your working code to the repository as you go.

Implement the Queue ADT using a growable circular array

Recall from day 1 of this course that when dealing with arrays that must grow in size, it is most efficient to double the capacity when the array is full, so that the expensive resizing operation occurs infrequently.

Your GrowableCircularArrayQueue class will implement the following operations specified by the Collections API: isEmpty(), clear(), size(), and contains(). You will also implement a toString() method for testing and convenience. The GrowableCircularArrayQueue will also implement the following operations specified by the Queue ADT: enqueue(), dequeue(), peek(). I added all of these to a nice SimpleQueue interface - make the GrowableCircularArrayQueue class implement that interface. 

 

Implementation requirements and hints:

  1. To make your work easier, we are only requiring you to grow the array when needed, and not requiring you to shrink it if many items are removed.
  2. As you know, resizing the array takes amortized O(1) time. We say amortized since doubling the capacity is O(n), but on average is O(1) since it occurs infrequently, as we learned on day 1.
  3. When implementing a stack, it is easy to make a remove method that runs in O(1) time. It is also possible to do this when implementing a queue, but it requires some thought . Note that when dequeuing items, you may not shift the array items over to fill the space, since that would require O(n) array accesses. Instead, make use of the empty space by "wrapping around" the array indices (like a circle) once you reach the end of the array. This is called a "circular" queue; ours also grows, so we need to be careful to track where to enqueue and dequeue items. Consider the following scenario:
    1. Create a new queue (so internal capacity = 5): [  |  |  |  |  ]
    2. Enqueue 8 items (so that the size is 8, but the capacity has doubled to 10). [ a | b | c | d | e | f | g | h |  |  ]
    3. Dequeue 5 of them (so that the size decreases to 3, but the capacity is still 10).  [  |  |  |  |  | f | g | h |  |  ]. (Of course, there is no need to delete the dequeued ones.)
    4. Enqueue 3 of them, which wraps around instead of growing the array. [ k |  |  |  |  | f | g | h | i  | j ].
    5. Enqueue 4 more, which will fill the array: [ k | L | m | n | o | f | g | h | i  | j ].
    6. Enqueue one more, which causes the array to double in capacity. You will probably find it simpler to re-order them: [ f | g | h | i | j | k | L | m | n | o |  |  |  |  |  |  |  |  |  |  |  ]
  4. You will need to decide which fields to use.
  5. I provided you with a couple of JUnit tests, including the scenario above. You may want to add more JUnit tests to check various expected behavior. If so, name your test cases in such a way that the name explains the test, like testThatEnqueueResizesArray() and testDequeuingUntilEmptyThenEnqueing().

Implement the Queue ADT using two stacks

You can implement a Queue using two stacks. How would you implement it? Don't worry too much about efficiency. We just want you to get more practice using one data structure to implement another one.  Like above, create a class, QueueFromStacks<T> that implements SimpleQueue<T> (and thus its methods). You'll need to add in toString() from scratch. Your implementation must use two java.util.Stacks as instance fields. How will you write enqueue and dequeue? There are a few different ways to do it, depending on whether you want enqueue or dequeue to be more efficient, or if you want to balance them. (The way I wrote it reminded me of a "Slinky" toy.)    

Analyze four implementations of the Queue ADT

The growable circular queue is an interesting implementation of a queue, but it is certainly not the only one. Here are three others and some questions to help you think:

  1. LinkedList. This is how Java does it. Enqueuing and dequeuing items are both efficient. How efficient? Why? Use what you know about linked lists.
  2. ArrayList. This implementation is very easy. Just call the array list's .add(item) and .remove(0) method to add to the tail of the list and remove from the head. However, this suffers one major performance issue. What is it?
  3. Two stacks. How efficient is your implementation above? There are a few correct answers here - of course, it will depend on how you wrote it.

For this part of the assignment, state the Big-Theta runtime of enqueue() and dequeue() for each of the four implementations. Then explain how each operation works in enough detail to justify the stated runtime. Record your answers in the Analysis.docx file in your Eclipse project and commit your work.

Write an expression evaluator

Programming languages must evaluate expressions following the syntax of the language. In this assignment, you will write a tool that will evaluate simple mathematical expressions given in different forms like 8 + 7 * 5 (infix) and 8 7 5 * + (postfix).

 

You are used to evaluating mathematical expressions that are written using infix notation, that is, each operator appears between the operands (numbers), such as 

4 * 5
or 
6 * ( 10 - 7 ).
However, that is not the only way to write expressions. In postfix notation, the operator is written after the operands. The previous examples would be written as 
4 5 *
and 
6 10 7 - *,
respectively.

Postfix notation has two advantages over infix notation. First, the order of operations is unambiguous without requiring parentheses. As we will see, 3 + ( 4 * 5 ) can be written as 3 4 5 * + , while ( 3 + 4 ) * 5 can be written as 3 4 + 5 *. Second, computers can evaluate postfix expressions easily using a stack.

In the very first example above, you can save the operands (4 and 5) on a stack and when you finally read an operator, just pop two operands and apply the operator. The second example works similarly - push the three operands (6, 10, and 7). When you read the - sign, pop the top two operands (7 and 10), apply the -, then push the answer back. When you read the * sign, pop the top two (3 and 6) and apply the * and push the answer. When you reach the end of the input, pop the answer. Your stack should now be empty - if not, the expression was malformed (too many operands). You can also detect if there were too many operators - can you see how?

Of course, calculators and computers don't require you to enter your expressions in postfix - they do it for you. Surprisingly, there is an algorithm to convert infix expressions to postfix that also uses a stack. Hint: in this postfix to infix conversion algorithm, the stack holds operators, not operands. If you try a couple examples, you'll see that this makes sense, since the order of the operands doesn't change, but the operators must somehow be stored and moved later in the output string.

So to evaluate infix, just convert it to postfix, then apply the algorithm described above!

Your starting code includes an abstract class called Evaluator, that has an abstract method to evaluate strings and return an int. You will write PostfixEvaluator and InfixEvaluator subclasses in which you will override this method. This is not the only way to do this, but is good extensible, object-oriented design. (Perhaps we might want to write a PrefixEvaluator later, who knows?)

We want you to use the infixToPostfix conversion algorithm as the first step of evaluating infix expressions, so the tests include specific tests to isolate that method. Note that this method takes a String argument and returns a String.

Hint: The starting code has errors. I tried to make it so that using Eclipse to fix the errors in the Main class will give you stubs of the classes and methods. It should even guess that InfixEvaluator should extend Evaluator and that the return type of infixToPostfix should be a String. If not, you can make these adjustments. You'll also need to add your own comments.

Requirements for the Evaluator

  1. Your algorithm must work in linear time with respect to the number of tokens (operators and operands). Thus, you may only read through the String once and build up the output string once using a loop - no backtracking or inserting output into arbitrary elements in the input string. (Exception: you may use two passes to evaluate infix expressions, one to convert to postfix and one to evaluate the postfix, in keeping with my statement above.) This also means we must build up the output using a StringBuilder, not a String - see the javadoc for StringBuilder for examples of how to use it if you haven't.
  2. Both algorithms must use a stack. For this section, you may use java.util.Stack instead of implementing your own.
  3. Neither algorithm can use recursion - recursion does use a stack internally, but we want the use of the stack to be explicit here.
  4. Both algorithms must handle the four basic operators (+, -, *, and /), plus exponents (^).
  5. For full credit, you must be able to handle parentheses in infix expressions.
  6. For full credit, you must throw ArithmeticExceptions when the input is malformed, as demonstrated in the tests.
  7. All math will be integer math, thus you will drop remainders during division if they occur.
  8. You must follow the standard order of operations precisely. Therefore you may not change the order things are added and you must apply operations of the same precedence from left to right. (In other words, you may not rely on addition and multiplication being commutative and associative.)

Simplifying Assumptions and Hints

  1. You may assume the tokens (operators and operands) in the input strings are all separated by spaces, thus making it easy to use a Scanner to parse the String one token at a time.
  2. You may assume that the only operands in the input will be non-negative integers.
  3. You may add whatever additional helper methods you need. For example, I added one to compare the precedence of the infix operators. 

Grading

Grading of the implementations will be based on unit tests and programming style (clear code including javadoc & internal comments).

I reserve the right to add unit tests and to change the point values of the given unit tests.

Grading of the analysis will be based on the runtimes and justification.

Tentative point distribution: queue implementations: 34 points, analysis: 16 points, evaluator: 50 points. Total = 100 points.