In this homework you will implement a generic Stack ADT using the dynamic array data structure. You will then use it to implement a simple desk calculator, which has a GUI interface (written for you).
The deadline for this assignment is unusual: it is due Monday after midterm examinations week. This is so that the deadline does not interfere with studying for the midterm examinations. However, the material covered in this Homework will be relevant for the midterm examinations. We recommend you finish it before the midterm examinations start.
A stack is a specialized kind of container with the following public operations (where “E” represents the element type):
super.clone()as explained in the textbook page 85.
For this homework, you will use the dynamic array data structure. You need to implement the invariant checker; we don't include tests since we wish you to demonstrate that you know how to use the freedom of selecting your own fields. Your invariant checker should check any redundany in your data structure; the more fields, the more to check. You also need to declare the public methods. Make sure to provide good documentation comments for all public entities (unless they override another public method).
One complication is the way Java handles generic arrays; to reduce the
complexity of this assignment, we provide you a
makeArray for making a generic array.
If the client provides a “class” value, then this code can actually
create the correct type of array, otherwise, it will need to “lie”
by using an object array. The “class” value is an aspect of
“reflection” in Java: where the program operates on elements of the
same program. Reflection is powerful and can be used in undisciplined ways
that break abstraction.
We minimize the use of reflection in this course and try to be
disciplined when we use it.
For this homework you will implement a desk calculator using two stacks, one for operands (long integers) and one for operators (e.g. “+”). Ignoring parentheses for now, we alternately accept numbers and operators from the input stream. The numbers are pushed on the operand stack, and the operators are pushed on the operator stack until they are ready for action. Binary operators such as addition are pushed onto the operator stack because we need to wait for a second operand, and because that operand may be claimed by a later operator. For example, suppose the input is
5 + 4 * 3 / 2 - 1The two stacks are added to as follows:
/arrives. This operator has equal precedence with the previous operator (
*) and so before going further, we activate the latter operator now since it has both operands (“4” and “3”). These are popped of the operand stack and the result (“12”) is pushed on the operand stack. Only then can the new operator be pushed:
At this point, we consider the next operator:
The top of the stack still is not lower precedence than subtraction, and so we activate the top operator again.
Now we can place the subtraction operator in the second stack and continue
Finally the calculator is told to “compute” and it activates all remaining operators in the stack.
Parentheses complicate this basic algorithm. Any number of left parentheses (calls to the open method) can occur before any operand. They are pushed on the operator stack, and are given a precedence lower than any operator. Then if a right parenthesis is read while we are looking for an operator, we activate all operators above the most recent left parenthesis and pop the left parenthesis as well, and try to read another operator. For example:
( ( 1 + 1 ) * 2 ) / 3 - 7The two stacks change as follows:
The calculator ADT encapsulates the stacks used above, a state (indicating what operations are legal) and (if we are in the “empty” state) a “default value” recalling the result of the most recent compute operation, which is used if the next computation starts with an operator. Initiallly the default value is zero. You don't need to write a well-formed-ness checker or add assertions in the implementations of the methods of this class.
The class provides the following public methods that indicate calculator actions:
valuemethod can be called when the calculator is in state 0 (Empty) or state 2 (Waiting) and in either case, the resulting state is 1 (Ready). If the calculator were in state 1, then calling value() throws an instance of IllegalStateException.
There are at least two possible designs. Either one can get full credit if implemented correctly.
In this design, as well as the two stacks, we have two fields: one to keep track of the default value and a boolean to indicate whether values or operators are expected. The “Empty” state means that both stacks are indeed empty.
The code needs to special case the
situation that the client calls
compute in the “Empty” state,
in which case the default value should be used to initialize the value
stack before running the normal operation. A special case is also
In this design, the default value is kept on the value stack. We keep an integer to reflect the current state (0, 1 or 2).
The code needs to special case the situation where the client calls
open in the empty state.
Don't leave “junk” (the default value)
in the value stack.
You need to complete the implementation of the
class and need to write the entire implementation of the
Calculator class (which should be in package
Your code for
Stack should check the invariant in assertions as
in past assignments. You will need to write and implement the data structure invariant.
Think about what could go wrong with the fields you declared.
You might it helpful to look at Homework # 2 or Lecture # 5 which
used a similar data structure.
Your code for Calculator should document every public method. It does not need an invariant.
Do not change anything else.
We provide the following files in your