Stack and JUnit Testing
PA 2: Stack and JUnit Testing
Final submission due: 1/19 (Tuesday) 11:59 pm
Checkpoint submission due: 1/16 (Saturday) 11:59 pm (extended)
100 points + 5 extra points (Checkpoint submission)
Overview
In this assignment, you will implement a stack and two stack applications. You will also write tests using JUnit.
This assignment is an individual assignment. You may ask Professors/TAs/Tutors for some guidance and help, but you can’t copy code. You may discuss the assignment conceptually with your classmates, including bugs that you ran into and how you fixed them. However, do not look at or copy code. This constitutes an Academic Integrity Violation.
START EARLY!
Style Requirements
You will be graded on your code’s style based on the style guide.
IntelliJ has a great plugin to check your style automatically. Use it!
There are style considerations beyond indentation and such.
● Choose names for test methods and for variables that are descriptive and useful when you see them in the test output.
● Consider writing helper methods if you repeatedly use the same set of statements.
● Use Javadoc comments for descriptions of your methods and classes and inline comments if the logic of your program is not captured by your variable names and the natural flow of code. Please do not comment on every line, your variables should be descriptive enough.
Checkpoint Submission
Similar to DSC 20, you can gain at most 5 points extra credit by making a checkpoint submission. The checkpoint submission is graded by completion, which is measured by some simple tests. In your final submission, you can modify the checkpoint part if necessary.
Files to submit:
● IntStack.java (the exception part is not required)
● IntStackTest.java (the exception part is not required)
■ With at least 3 assertions for each implemented method. You can add more later.
Part 0 - Setup
Part 0.1 Starter code
Tutorial on how to obtain the Starter Code
Part 0.2 PA Quiz
Total: 5 points
Take the PA2 quiz on canvas so we can check that you understood the write-up. You can take the quiz 5 times before the deadline. We will take your best submission. Be sure that you have read the whole PA before starting the assignment!
Part 0.3 Style Requirements
Total: 10 points
You will be graded for the style of programming on every assignment. Each assignment will have about 10 points just for the style of your code, so make sure you read through this part and strictly follow the style requirements when writing your PAs. You may find the style guide on the course website.
This is a complete Java style guide: Java Style Guide written by Alan Yao from UC Berkeley.
Part 0.4 Requirements
1. Do not modify declarations and method signatures in the starter code.
2. You cannot import any packages, except java.util.EmptyStackException. For test files, you can have the necessary JUnit imports, but try to not import other packages.
3. Do not hardcode answers.
Part 1 - Resizable Int Stack
Part 1.1 Introduction
Recall that a stack is an abstract data type (ADT) that allows only a limited number of operations on a collection of data. Elements are stored and removed in Last-in First-out (LIFO) order. In Part 1, you will implement a class IntStack using an integer array in IntStack.java file.
In addition to the basic operations that Stack ADT has (e.g. push, pop, peek), the IntStack will have several special features which will be explained below. Make sure you understand how IntStack works before going into the implementation details.
● Size: The size of IntStack represents the number of elements within it.
● Capacity: The capacity of IntStack represents the maximum number of elements that the current IntStack can contain. In other words, it is the size of the integer array used by IntStack.
● Resizing: The capacity of the IntStack should be able to expand & shrink depending on the number of elements. (The reason behind this is that we want to push an arbitrary number of integers into the stack, but we cannot initialize an infinitely large array and we do not want to have too much memory taken up by unused array slots. That is why we want to have a dynamically resizing feature.)
○ Expanding - Load factor: The load factor is a decimal (0.67 <= LF <= 1 for this PA) which measures how full the array is allowed to get before its capacity is automatically increased. When size/capacity >= load factor, the capacity should be doubled.
new capacity = old capacity * 2
○ Shrinking - Shrink factor: The shrink factor is a decimal (0 < SF <= 0.33 for this PA) which measures how empty the array is allowed to get before its capacity is automatically decreased. When size/capacity <= shrink factor, the capacity should be halved.
new capacity = old capacity / 2
However, you should make sure that your capacity will never become less than the initial array capacity. For example, if you initialized the stack with the capacity of 5, and your current capacity is 5 before shrinking, then the capacity should stay as 5.
● Exceptions: Your IntStack will need to throw certain exceptions under several circumstances (as described in the implementation details). You would also need to import the specified exceptions. Do not include throws Exception in the method headers because the thrown exceptions are Runtime Exceptions. (Recall the difference between checked vs unchecked exceptions).
Part 1.2 Implementation
|
Constructors and methods to implement in IntStack.java |
|
public IntStack(int capacity, double loadF, double shrinkF) Constructor that initializes a stack with the given capacity, load factor and shrink factor. The valid range of capacity is (CAP >= 5), that of load factor is (0.67 <= LF <=1), and that of shrink factor is (0 < SF <= 0.33). @throws IllegalArgumentException if capacity, loadF or shrinkF is out of valid range |
|
public IntStack(int capacity, double loadF) Constructor that initializes a stack with the given initial capacity, the given load factor, and the default shrink factor (0.25). Hint: Do not repeat yourself! You might find “this( )” useful. @throws IllegalArgumentException if capacity or loadF is out of valid range |
|
public IntStack(int capacity) Constructor that initializes a stack with the given initial capacity, the default load factor (0.75), and the default shrink factor (0.25). |
|
Hint: Do not repeat yourself! You might find “this( )” useful. @throws IllegalArgumentException if capacity is out of valid range |
|
public boolean isEmpty( ) Checks if the stack is empty. Returns true if it is empty, false otherwise. |
|
public void clear( ) Clears all elements in the stack. After clearing, the capacity of your stack should be reset to the initial capacity. |
|
public int size( ) Returns the number of elements currently stored in the stack. |
|
public int capacity( ) Returns the maximum number of elements the stack currently can store. In other words, the length of the backed data array. |
|
public int peek( ) Returns the top element of the stack. @throws EmptyStackException if the stack is empty |
|
public void push(int element) Pushes the given element to the stack. Double the capacity of the stack before pushing the element if the condition meets. |
|
public int pop( ) Returns and removes the top element of the stack. Half the capacity of the stack after popping the element if the condition meets. Note that if after shrinking, the stack will be smaller than the initial capacity, resize it to the initial capacity. |
|
@throws EmptyStackException if the stack is empty |
|
public void multiPush(int[ ] elements) Pushes all numbers in the array elements to the stack. Elements in the front of the array elements (at index 0) should be pushed to the stack first. @throws IllegalArgumentException if elements is null |
|
public int[ ] multiPop(int amount) Pops the given amount of elements from the stack. If the stack does not have the given amount of elements, pop all elements from the stack. Returns an int array that contains all popped elements. Elements popped first should be placed in the front of the output array. The length of the returned array should be identical to the number of elements you popped. @throws IllegalArgumentException if amount is not a positive number |
Part 1.3 JUnit Testing
For this part, you must use JUnit to test your code. Create a JUnit 4 test file called IntStackTest.java, and include at least 3 assertions (tests) for each constructor and methods. In addition to that, you should test all possible cases that throw an exception (there’s an example in the ImageEditor sample test file). For test files, we will not grade on style, so you don’t need to worry about style requirements like magic numbers, comments and headers. This test file will be a part of your submission.
Part 2 - Image Editor
Part 2.1 Introduction
In Part 2, you will use IntStack class to implement an image editor in ImageEditor.java file. The image editor will maintain the current image, and provides several painting operations along with an undo/redo functionality. The details of how these works is explained as follows:
● Image: Image will be represented by a 2D array of integers. Each element represents the color value of a specific pixel.
○ Pixel Color: The integers stored in the 2D array represent the color value of a specific pixel. The color value is in the range of 0 and 255 inclusively.
○ Pixel Position: The indices of the 2D array represent the position of the pixels. The rows and columns of the 2D array correspond to the rows and columns of the image. (e.g. arr[0][3] stores the color of the pixel at the 0th row, 3rd column of the image)
● Painting operations: The user can use the following 3 options to edit a pixel’s color.
○ Scale: Update a specific pixel’s color by multiplying the original color value by the given scaling factor. If the color value exceeds 255, the new color value should be set to 255.
○ Assign: Assign a new color value (between 0 and 255, both inclusive) to a pixel.
○ Delete: Set a specific pixel’s color value to zero.
● Undo/Redo: Undo the previous operation or redo the next operation (imagine the same commands you have for any editors). You will implement these features by making use of IntStack.
○ Undo: The undo IntStack will maintain a history of the painted pixels.
■ Whenever one of the above painting operations is made to a pixel, you should push the 3 integer values of that pixel (row number, column number, and the ORIGINAL color value) to the undo stack before painting the pixel. This way, you will be able to undo an operation by popping out the 3 values from the undo stack and change the pixel’s color back to its original. (This means, in order to make undo work, you need to handle the undo stack in multiple methods in addition to the undo method.)
■ Redo is also considered as applying a painting operation, so you need to update the undo stack when redoing as well.
○ Redo: The redo IntStack will maintain a series of operations that have been undone.
■ Before undoing, you should push the 3 values of that pixel (row number, column number, and the CURRENT color value) to the redo stack. This way, you will be able to redo an undone operation by popping out the 3 values from the redo stack and repaint the pixel.
■ The redo stack should be emptied before any painting operation is newly made.
● Exceptions: Again you will need to throw certain exceptions under several circumstances (as described in the implementation details). Do NOT include throws Exception in the method headers.
Part 2.2 Implementation
public ImageEditor(int[ ][ ] image)
Constructor that initializes the image with the given image, and initializes two stacks for undo and redo with capacity of 30.
@throws IllegalArgumentException if image’s width (# of columns) or height (# of rows) is zero, or if each row of image is not equal (meaning the image is not rectangular but distorted)
public int[ ][ ] getImage( )
Returns the image as a 2D array.
public void scale(int i, int j, double scaleFactor)
Multiplies the color value of the pixel at the given position by the given scale factor. i represents the row number, and j represents the column number. The valid range for i is (0 <= i < height), for j is (0 <= j < width), and for scale factor is (0 <= SF). If the new color value exceeds 255, set the new color value as 255.
Make sure to cast the calculated value to int before overwriting the color, i.e. “(int) (oldValue * scaleFactor)”, to prevent potential rounding issues.
@throws IndexOutOfBoundsException if i or j is out of the image frame
@throws IllegalArgumentException if scaleFactor is out of valid range
public void assign(int i, int j, int color)
Assigns a given color value to the pixel at the given position. The valid range of color is (0 <= color <= 255).
@throws IndexOutOfBoundsException if i or j is out of the image frame
@throws IllegalArgumentException if color is out of valid range
public void delete(int i, int j)
Sets the color value of the pixel at the given position as zero.
Hint:
You may find a shortcut here: think about what is the equivalent operation of delete( ).
@throws IndexOutOfBoundsException if i or j is out of the image frame
public boolean undo( )
Updates the image by undoing the latest operation. Returns false if there’s no operation to undo, and true if undo was successful. Make sure it does not throw an EmptyStackException.
public boolean redo( )
Updates the image by redoing the next operation. Returns false if there’s no operation to redo, and true if redo was successful. Make sure it does not throw an EmptyStackException.
Part 2.3 Testing
For this question testing is for your own benefit. You can test your code using either JUnit, print statements, or IntelliJ debugger. You don’t need to submit any test cases with your code.
Since this question involves 2D arrays, you will need to iterate through the first dimension to check the contents, otherwise you can only see an array of memory addresses instead of actual contents.
We strongly recommend you to write JUnit test cases for this question, since you can use a combination of all assert statements we covered in class to test it. This will be a good practice for your JUnit skills. More importantly, you might find JUnit works better than print statements when testing 2D arrays. We have provided a sample test file (ImageEditorTest.java) in the starter code. You should understand what the sample file is doing, and feel free to implement more test cases in the sample file.
Part 3 - Arithmetic Expression Decomposer
Part 3.1 Introduction
Restriction
You must use a stack to solve this problem.
Description
In Part 3, you will implement a method that will decompose a normal arithmetic expression into a special kind of expression within the ExprDecomposer.java file.
The normal expression that we are familiar with is having the operators between the operands, e.g. (1 + (2 * 1)) + (2 + 3). On the contrary, this special expression will have the operators appearing after the operands, e.g. 1 2 1 * + 2 3 + +.
To keep things simple, we will only consider non-negative, single-digit integers, and basic arithmetic operations. You can see the specific assumptions in the implementation details below. Also, you may get familiar with the conversion from the normal expression to the special expression by the following examples:
Normal expression
Special Expression
1 + 2
1 2 +
(1 + 2) + 3
1 2 + 3 +
1 + (2 + 3)
1 2 3 + +
(1 + 2) + (3 + 4)
1 2 + 3 4 + +
((1 - 2) / 3) * (4 + 5)
1 2 - 3 / 4 5 + *
1 + (2 * (3 + (4 - 5)))
1 2 3 4 5 - + * +
(((1 + 2) * 3) + 4) - 5
1 2 + 3 * 4 + 5 -
Task
To implement the decomposer, you have two main tasks:
1. Create a CharStack inner class by copy-pasting the IntStack class you have implemented and replacing int with char to make the stack accommodate characters instead. To save you some work, you may delete methods and variables that you will not use to implement the decomposer, but you must keep properly functioning push( ) and pop( ).
2. Using the CharStack, implement the decomposer using the algorithm described as follows.
Algorithm Explanation
● Intuition to the algorithm
○ Notice that the order of the numbers in the normal expression is the same as the special expression. The only difference is that the special expression will 1) have the operators at different positions and 2) have no parentheses. This tells us that we can create the special expression by removing the parentheses and by changing the positions of the operators. Furthermore, the second difference shows that the positioning of the operators inherits the functionality of the parentheses. What we can conclude from this is that the parentheses in the normal expression can tell us where to position the operators in the special expression.
● Each step of the algorithm
○ We will traverse through each character of the given expression. You can break the characters into four cases: digit, operator, parentheses and spaces. For spaces you can ignore them, but for other characters, you have to figure out when and how to make use of a stack to achieve the purpose. Here are some hints of what you should consider:
■ When the character is a digit: Look at the examples, and think about what is the position and relative order of digits. Especially think about its position relative to the operator which this digit is associated with.
■ When the character is an operator: In normal expressions, an operator is followed by the second operand; in special expressions, an operator follows the second operand. Hence, we will not append the operator to the output array now, but wait until we have handled the second operand. Notice that the operand can be not only numbers, but also sub-expressions surrounded by parentheses (For example: “1 + (2 + 3)”).
■ When the character is one of the parentheses: In the “(a + b)” format, a left parenthesis always denotes the start of a sub-expression and is always before the first operand, and a right parenthesis always denotes the end and is always after the second operand. This means when we see a ‘(‘, we are starting to decompose a sub-expression, and when we see a ‘)’, we are done with that sub-expression. Now, go back to the previous bullet pointagain, and try to figure out the relationship between operators and parentheses. Also, notice that parentheses are not included in the output.
○ We should take care of one edge case: There might exist an expression that is not wrapped around by a pair of parentheses, and the algorithm above uses parentheses to detect the start and end of expression. How should we handle this case? Check our assumptions below to understand when it will happen.
Part 3.2 Implementation
In the starter code, we have provided two utility methods for you: isDigit( ) and isOperator( ). Make sure you understand what they are doing, and feel free to use them in your code. We have also provided a skeleton of the inner class CharStack, so that you can copy & paste your implementation to this skeleton and do necessary modifications. Notice that you should NOT modify the given declarations in the starter code, and it’s better to check if the declarations are accidentally changed after finishing your implementation.
After doing all of this, implement the core method of this part:
|
Method to implement in ExprDecomposer.java |
||||||||||||||
|
public char[ ] decompose(String expr) Decomposes the given arithmetic expression and returns the decomposed tokens as a char array. Assumptions: Assume expr will always be in the valid form:
|
||||||||||||||
|
Examples of valid expressions: “9 * 4”, “(1 + 2) + 3”, “( ( 1 / 2 ) * (3 + 4) ) + ( (5 - 6) + 7 )” Examples of invalid expressions (which will never be passed in as expr so you don’t need to worry about handling these situations): “(1 ++ (2 * 3)” violates 1: invalid syntax (two ‘+’s, missing 1 right parenthesis) “10 * -20” violates 2: has multiple digits and negative number “5 % 2” violates 3: invalid operator ‘%’ “(1 + 1) * (8 + 2) * 2” violates 4: missing some ( ) to surround sub-expressions “5 + 2!” violates 5: contains invalid character (‘!’) Examples:
|
||||||||||||||
Part 3.3 Testing
For this question testing is for your own benefit. You can test your code using either JUnit, print statements, or IntelliJ debugger. You don’t need to submit any test cases with your code.
Submission
Checkpoint Submission (Optional, Extra Credit):
Files to submit:
● IntStack.java (the exception part is not required)
● IntStackTest.java (the exception part is not required)
Final Submission:
Make sure all files are in src/ folder!
Files to submit (4):
● IntStack.java
● IntStackTest.java
● ImageEditor.java
● ExprDecomposer.java
To submit your files, you will need to push your code to your private Github repo first, then turn in those files on GradeScope by selecting Github as the submission method.
After you submit your files to GradeScope, wait for the output of the submission script. Make sure you see this after your submission:
THIS IS A SUCCESSFUL SUBMISSION. YOUR SCORE WILL BE UPDATED ONCE GRADED.
Otherwise, please fix the error and resubmit your files.
2021-01-18
Implement a stack and two stack applications.