$24
Lab Assignment 5 (Pair Programming) Solution
Random Access Files, Collections, Generics
Concepts
Review exceptions
Review random access files
Review simple GUI (graphical user interfaces) Review generics
Review collections Review linked lists
Problem Specification
Develop a Java application that reads data (expressions as a kind of a linked list of characters, as described below) from one of three random access (binary) files and reconstructs the corresponding postfix expressions (based on what was read from the input file). These two steps are referred to as “decoding” in this assignment. After decoding, your application should evaluate the results of the expressions using a stack, and display the result (in the format indicated below). The application should utilize a graphical user interface to interact with the user.
Arithmetic Notations:
In Arithmetic, there are three types of notations for expressions. For the expression “2 + 4”, the corresponding notations are shown below.
prefix notation (a.k.a. Polish notation): operators are written before the numbers to which they apply; e.g. “+,2,4”
postfix notation(a.k.a. reverse Polish notation): operators are written after the numbers to which they apply; e.g. “2,4,+ “
infix notation: this is the notation we are most familiar with - operators are placed between the numbers to which they apply; e.g. “2 + 4” (note that both prefix and postfix notations do not require parentheses to indicate the required order of operations used in them, while the infix notation requires parentheses)
For more information on postfix, you may refer to the following websites: http://www.cs.man.ac.uk/~pjj/cs212/fix.html https://en.wikipedia.org/wiki/Polish_notation
1
CS 1120 Fall 2017
LA5
Random Access Files, Generics, Collections, Etc.
The following guidelines explain how the random access files were “encoded” (i.e., the format of the data in the file).
The postfix expressions are in the following format. The “comma” is used as delimiter.
21,5,+,3,14,5,+,*,+ (which is equal to the infix expression (21+5)+3*(14+5) = 83)
Each of the three binary files contains two postfix expressions. The expressions are made up of characters (chars) including commas. The numbers are stored as chars too; for example, 21 would be stored as two chars: ‘2’ and ‘1’.
The characters are stored in the binary files at random locations (not sequential).
Each character is followed by an integer, which is the location index of the next character (the byte number relative to beginning of the file).
The first two bytes in each binary file represent the first character of a postfix expression. Then the following 4 bytes represent the location index of the next character.
Recall that two bytes are required to store chars while four bytes are required to store ints.
-1 indicates the end of the current expression. The byte following “-1” is the beginning of the next expression.
-1000 indicates the end of the last expression (since there is more than one expression in each file).
An example output is provided below. Your program should give a similar output.
Example Output:
Reconstructed expressions (character, its relative location in the file):
1st expression
96914
34584 , 42501
37717 , 26493 + 68416 , 81287
75874 , 15125
56643
2
CS 1120 Fall 2017
LA5
Random Access Files, Generics, Collections, Etc.
91719 , 99414
13804 , 6996 + 55592 , 94758 * 58363 , 75425 + -1
// End of the 1st expression // 2nd expression starts
6162
45464 , 21614
90293
19997 , 88762
40457
42453 , 32975
73527
26644 , 362 / 33219 , 26154 + 93272 , 11695 * -1000
End of the 2nd expression
Processing expressions from Expression1.dat ...
Number of Expressions: 2
----------------------------
Expression 1: 21,5,+,3,14,5,+,*,+
Result: 83
Expression 2: 28,32,54,80,/,+,*
Result: 896
Design Requirements
You need to use a stack to evaluate the expressions. A stack follows the “Last in First Out” (LIFO) scheme when reading data stored in it. See Hints below for description of the stack data structure.
You are required to use a Linked List (which has nodes) to implement your stack.
You are not to use the Java-defined Stack, LinkedList or Node classes. You will need to write your own classes using the interfaces provided.
The Linked List should perform insertions at and deletions from the end of the list.
3
CS 1120 Fall 2017
LA5
Random Access Files, Generics, Collections, Etc.
The LinkedList class should be singly linked and use nodes (objects of the Node class) to store its data. The nodes in a LinkedList object should be indexed starting from 0. For example, if a LinkedList object has 4 nodes, the index of the first node should be 0 (zero) and the index of the last node 3.
Use the following class names:
LinkedList (implements ILinkedList interface),
Stack (implements IStack interface),
Node (implements INode interface),
Decoder (implements IDecoder interface),
PostfixExpression (implements IPostfixExpression interface) and
PostfixMain (for the class with the main method and the GUI code).
Your application must implement the following interfaces:
public interface IStack<E {
/**
Adds the parameter s to the top of the stack.
@param s - the string to be added
*/
void push(E s);
/**
Removes the top element from the stack
@return - the top element in the stack */
E pop();
/**
Returns the top element on the stack without removing it.
@return - the top element in the stack
*/
E peek();
/**
Returns the number of elements in the stack.
@return - the number of elements in the stack */
int size();
/**
Returns true if the stack contains no elements; false otherwise.
@return - true if the stack contains no elements; false otherwise. */
boolean isEmpty();
}
public interface ILinkedList<E {
/**
Adds the element e to the end of the list (appends it).
@param e - element to be added
*/
void add(E e);
4
CS 1120 Fall 2017
LA5
Random Access Files, Generics, Collections, Etc.
/**
Removes all of the elements from the list */
void clear();
/**
Returns the element at the end (index size-1) of the list.
@return the element at the end (index size-1) of the list. */
E getLast();
/**
Returns the element at the specified index in the list.
@param - Index of the element to retrieve. (Indexing starts from 0.)
@return - the element at that index.
@throws IndexOutOfBoundsException
*/
E get(int index) throws IndexOutOfBoundsException;
/**
Returns true if the list is empty; false otherwise.
@return true if the list is empty, false otherwise. */
boolean isEmpty();
/**
Removes the element at the specified index.
@param - Index of element to be removed. (Indexing starts from 0.)
@return - The contents of the element that was removed.
@throws IndexOutOfBoundsException
*/
E remove(int index) throws IndexOutOfBoundsException;
/**
Returns the number of elements in this list.
@return the number of elements in this list. */
int size();
}
public interface INode<E {
/**
Returns the data stored in this node.
@return - Data in this node.
*/
E getData();
/**
* Setter for data for this node.
* @param data - New data
*/
void setData(E data);
/**
* Returns the node next to this node.
5
CS 1120 Fall 2017
LA5
Random Access Files, Generics, Collections, Etc.
@return - Node next to this node. */
INode<E getNext();
/**
* Sets node received as the next node to this node.
* @param next - new next node.
*/
void setNext(INode<E next);
}
public interface IPostfixExpression {
/**
Calculates the result of the expression using a stack and returns it.
@return - the result obtained for the expression.
*/
int calculateResult();
/**
Returns the arithmetic expression in string format.
@return - the result obtained for the expression. */
String getPostfixExpression();
/**
* Sets the arithmetic expression (in string format).
* @param expression - the new expression.
*/
void setPostfixExpression(String expression);
/**
Sets the IStack attribute in this class.
@param stack - the new stack.
*/
void setStack(IStack stack);
}
public interface IDecoder {
/**
* Sets the IPostFixExpression attribute in this class.
* @param expression - the new expression.
*/
public void setPostfixExpression(IPostFixExpression expression);
/**
Reads the expression from the input file, stores it as a String,
creates a Postfix object and sets the expression attribute for the
Postfix object (using the String from the input file), calls the
calculateResult() method (using the Postfix object) and prints out
the result of the expression (which is returned from the call to the
calculateResult method).
@param fileName - the name of the input file to be read.
6
CS 1120 Fall 2017
LA5
Random Access Files, Generics, Collections, Etc.
*/
public void processExpressions(String fileName);
}
You need to develop a simple GUI for your application to interact with the user.
Your GUI should have three buttons: one for each binary file you’re provided with (as shown in the figure above).
To decode and evaluate the expressions in the first binary file, the user would need to click on the button for that file; similarly for the second and third binary file. You will need to display appropriate instructions to the user in your GUI, and buttons should have appropriate labels to clearly inform the user what they are for.
For your GUI, if you choose to use colors other than the default ones, you will need to carefully select a color scheme with enough contrast so that the labels can be clearly read. For example, white text on a cream-colored background will not be as easy to read as white text on a darker background.
Your GUI class should have an embedded main method. The main method in this class should have just the single line of code as shown below.
public class PostFixMain {
// ... Code for your GUI
public static void main(String[] args) { new PostFixMain();
}
}
You must use try-catch blocks where appropriate to ensure your application gracefully handles any exceptions that may be thrown. Note that using the “throws” clause will not be sufficient as it will not prevent your application from crashing if there is a problem when trying to access an input file.
To test your program, use the provided binary files
Hints:
A stack is a data structure which allows a user to add objects (push) or remove objects (pop) from one end only.
An example of this is the call stack seen in the Eclipse Debugging Perspective. In that case, since the main method is always the first method to be called when a program is executed, it is the first method to be “pushed” onto the stack and the last method to be “popped” off the stack.
In this assignment, after decoding the data in a binary file (and reconstructing the postfix expression), the operands and operators are comma-delimited (i.e. separated by commas). As you read the expression, any operand encountered should be pushed onto the stack. When an
7
CS 1120 Fall 2017
LA5
Random Access Files, Generics, Collections, Etc.
operator is encountered (since each of the operators used in this assignment require exactly two operands, the two topmost objects on the stack should be popped off the stack and the operator should be applied to them (e.g., in the expression “2+4”, the ‘+’ requires two operands: 2 and 4). The result of that operation should then be pushed back onto the stack. This process should keep repeating until everything has been read; at this point, there should be only one object on the stack - the result.
You may want to complete the implementation of the application without GUI first, and then add the GUI so that you are focusing on fewer things at a time (“divide and conquer”).
The type parameter ‘E’ is defined when a Stack object is instantiated, and the specified type then is passed to the LinkedList class (used to implement a stack), and finally to the Node class (used to represent the nodes in the LinkedList object).
The input files are random access files. Start reading from the file with the parameter for the seek() method set to zero (i.e. seek(0)). A char is stored starting from byte 0 (index 0) in the file; this is followed by an int which is the starting byte index for the next char (so this int will be the next parameter for your seek() method). This sequence (char, int, char, int, …) continues till -1000 is encountered, signifying the end of the expressions stored in that file.
Do not confuse file indices (in bytes) from linked list indices (expressed as node number starting from 0).
Additional Requirements
Pair Programming
You have received emails notifying you of GitLab accounts created for you, with instructions on how to reset your passwords. You will need to work on this assignment with those with whom you have been paired up.
As explained in the lab, there should be a visible evidence of both partners in a team contributing to the work required for this assignment. You will be graded on how well you use your GIT repository. The “commits” on GitLab will be reviewed to determine if there was input from both team members. There should be at least two commits from each person on the team. In addition, after Phase 9 in the SLC report, a brief explanation should be included explaining what each team member worked on.
You must add the lab instructor to your GIT repository to provide access for grading purposes. The “Git Guide” document posted on the Content page in Elearning includes steps for specifying how to utilize Git.
If you experience any problems with Git, get in touch with the lab instructor at the earliest opportunity. A zip file containing your submission needs to be submitted to Elearning only if you can’t get Git working (you will be penalized for this, so you need to make every effort to work with Git). If your code is in the repository, you will not have to upload it to Elearning. However, you still need to keep to the due date for submission – note that the most recent date/time of modification can be seen in Git.
8
CS 1120 Fall 2017
LA5
Random Access Files, Generics, Collections, Etc.
Software Life Cycle Report with UML diagrams
You are required to follow the Software Life Cycle (SLC) methodology presented in class, and write the SLC Report, explaining how you followed the nine phases of the Software Life Cycle in this assignment.
This report is to be submitted to the LA5 dropbox folder in Elearning.
For this LA, you are also required to provide the UML diagram for your application, showing all classes, their fields/attributes and the methods they provide. You should also show the class hierarchy. Your UML diagrams should be included in Part 1 of Phase 2 of your SLC. Please note that UML diagrams must be drawn using an appropriate program (e.g., MS Paint or MS Powerpoint). Handwritten UML diagrams will receive no credit.
A proper design (with stepwise pseudocode refinement), a proper coding method (with stepwise code refinement starting from the most detailed pseudocode refinement), and proper testing are all essential. For reference, please see the Sample SLC Report (covered in class) on Elearning.
Note: Correct pseudocode development will be worth 30% of the total LA grade.
You will need to generate Javadoc for your project. Follow the steps shown in class (a copy of these steps can be found on the Content page in Elearning). If you follow the steps accurately, a “doc” folder (for Javadoc) should be created in your project.
Coding Standards
You must adhere to all conventions in the CS 1120 Java coding standards (available on Elearning for your Lab). This includes the use of white spaces and indentations for readability, and the use of comments to explain the meaning of various methods and attributes. Be sure to follow the conventions also for naming classes, variables, method parameters and methods.
Assignment Submission
The final version of your project should be uploaded to the GitLab repository (a Git push) by the due date / time.
The SLC reports should be submitted to the appropriate folder on Elearning. Only one SLC report is required for each team / pair and the names of the team members should be clearly indicated on the report.
NOTE: The Elearning folder for LA submission will remain open for only one day beyond the due date and will indicate by how many days you missed the assignment deadline.
All assignments must be submitted by Friday 12/8/17 at the latest as this is the last week of classes.
The penalty for late submissions as stated in the course syllabus will be applied in grading any assignment submitted late. Remember to turn in your LA even if not completed by 12/8/17 – since a student who does not submit 2 or more LAs will earn a failing grade in the class (even with perfect scores earned in the remaining LAs, exams, etc.)
9
