In this lab you will work with several partners to create a data structure and extend it to solve problems. Besides learning the data structure and the value of interfaces, I hope that you will also become acquainted with:
· paired programming
· reading and adding to other programmers' code
· other class members
To prepare for this lab, before the lab you should:
· Read the text chapters associated with big-O notation, stack, and link lists (I recommend bringing the text book to the lab.)
· Read this lab description.
· Answer the questions in pre-lab assignment in a text file called polynomial.txt and submit your answers in infixToPrefix.txt to cs2321, secGlab or secIlab, preLab1, where secGlab is for students participating in a group labs and secIlab is for students participating in an individual labs.
If you are performing this lab alone you are to do all parts the lab individually before the due data including the pre-lab assignment.
The instructor will divide the class into pairs, assigning one partner as A and the other as B. At a single computer, the partners code a basic data structure in A's home directory. At the end of the lab period, approximately 120 minutes, the partners should have finished implementing and debugging the data structure, singly linked list, and will save the file in A’s home directory
In the next lab period the partnerships will change by partner B leaving A to join a new A. The new partnership will code up the extensions to the basic data structure for a specific amount of time, 60 to 90 minutes, now in B's home directory. This implies that the original code in A's home directory has been transferred to B's home directory, perhaps by email. Also you will want to cut and paste the classes, code, from the previous lab into the new code.
At the end of the specified time the partnership will change as before but now A will leave B and B will keep the code. The new partnership will further extend the data structure for a specified time, approximately one half hour. At the end of the allotted time B will submit the code that was created by the three partnerships. In the comments each partnership will be clearly stated.
In particular the pairs will code:
1. Singly linked list
2. Linked list implementation of a stack
3. Using the stack to convert infix expressions to prefix expressions.
Arithmetic expression has three general forms infix, prefix, and postfix. Each form has a particular advantage for parsing and evaluating. The terms specify the location of the operator. Infix is between the operands of the operator, prefix the operator is before the operands, and in postfix the operand appears after the operands.
For simplicity we will only consider operator +, -, *, and /. Also the operators operate on only two operands. You are probably most familiar with infix expressions, so examples of fully parenthetic representation:
· (a + b)
· ((a + b) – c)
· ((a * b) – (d + e))
Note that the outer parentheses are required in fully parenthetic representation. This lab will assume that the infix expression is fully parenthesized. Also notice that each operator has only two operands, in other there are no expressions like a + b + c. In the last two examples some are operands are results from nested operations.
You are also familiar with the prefix form for the expression. Prefix expression is similar to the functional form in mathematics. The infix form the examples above are:
· +(a, b)
· -(+(a, b), c)
· -(*(a, b), +(d, e))
Note that prefix form elicits the functional meaning of the operator, and clearly indicates the source of the operators. The form is also use fully for tree representations of expressions.
You are probably less familiar with postfix form for an expression. It is similar to the notation of HP calculators. The postfix form for the examples above are:
· a, b +
· a, b + c –
· a, b * d, e + -
Note that form does not require parenthesis, and smaller stack can be used to evaluate the expressions because operators are not pushed on the stack.
Partner A should download SNodeList.java in his/her home directory (preferably in a sub-directory called cs2321Lab1, for example) and open it in a text editor of the partnership’s choice. You can do this by either saving the page to your home to the sub-directory or copying the text in the web page and pasting it in your text editor.
Notice that the file contains completed classes:
·
InvalidPositionException
·
BoundaryViolationException
· SNode – singly linked node
The file also contains interfaces:
·
Position
·
List
The file contains a single unfinished class:
SNodeList
During this phase of the lab you finish SNodeList, a singly list node implementation of the List interface.
You should first study the SNode class, a singly linked node implementation of the Position interface, and be sure you understand it. It contains the private fields element (the Object contained by the node) and next (a reference to the next SNode). The methods are basically sets and gets.
Second, you should study the List interface. This is the interface that you will implement with SNodeList using SNode. The methods in List are in the order that I expect that you will write them. You will notice that I have included some implementation hints, these are generally commented using “//.”
Third, you should study what is already written in SNodeList class. Note that the methods you will finish return null when they return an object. Naturally the completed method will generally not return null; the null return is there only so the incomplete methods will compile. SNodeList already has all the private fields you should need. Also included in SNodeList is the main method. It is set up to read the inputs from the keyboard, this is called the standard input. You are to add to main to test and demonstrate that your program is correct. There are hint-comments in the main method to show you where to write debugging code. You should leave all your debugging code in place. If they produce too much output, you can comment out portions of the debugging codes, better is to put them inside an if-statement, something like:
Boolean
DEBUG_SOMETHING = true;
if (DEBUG_SOMETHING) { /* do and print
something */ }
Note that the inputting will terminate after an end-of-file is encountered, which can be simulated with a “control-d” at the keyboard. You may want to repeat a long test many times until the program runs correctly. In this case you may want to write your inputs in a file, and redirect java’s input by using:
java SNodeList < inputFile
where inputFile is a file containing your inputs. The input file does not need a “control-d” to be terminated; in fact it should not have a “control-d.” If the output is long you may want to redirect java’s output by using
java SNodeList > outputFile
and outputFile will be generated in the same directory. You can inspect the output file with any text editor. Naturally, you can redirect both input and output:
java SNodeList < inputFile > outputFile
Now you can finish the implementing List in SNodeList. First add comments to the top the file identifying partner A and B below the comments identifying the file. Implement all of List and thoroughly debug all SNodeList’s methods. Note that there is file inList.txt as an example input, can you can use as testing. I recommend insuring that your program compiles at all time by testing compilation and running after each modification and addition.
In the second period partner B will be directed to sit with a new A partner. At this time the new partner A should transfer the SNodeList.java to partner B’s home directory, preferably in a sub-directory, by email. Partner B should also download ListStack.java into the same sub-directory. You will want to get and paste the content of SNodeList.java into the ListStack.java, below the ListStack code. Be sure to includes the comments. ListStack.java will not compile unless you have assured that there are no duplicate import-statement, and only a single public class, ListStack, in this case.
Notice that the file contains completed class:
EmptyStackException
The file also contains interface:
Stack
The file contains a single unfinished class:
ListStack
During this phase of the lab you finish ListStack, a list
implementation of the Stack interface.
First, study Stack, the interface that you will implement with ListStack.
Secnod, study the incomplete class ListStack. Again incomplete methods return null, only so they will compile, and the finished methods will generally not return null. Note that ListStack does not have explicit private fields. Does it need any? Are there any implicit fields, and if yes what are they? Again main contains code for inputting the terms.
Now you are ready to finish ListStack and implement Stack. First add comments to the top the file identifying partner A and B below the comments identifying the file. Again, you are expected to thoroughly debug your implementation and write your debugging code in the main method. While debugging ListStack, you may find errors in SNodeList; you will need to fix the bugs. Leave all your code in place.
When time is called partner A will be directed to sit with a new B partner. The partnership can continue working in B’s home directory. Partner B can download InfixToPrefix.java into the same sub-directory. You will now cut and paste ListStack.java, below the InfixToPrefix code. Assure that it will compile by having only one import statement and public class.
The file contains a single unfinished class:
InfixToPrefix
During this phase of the lab you finish InfixToPrefix,
a class that reads an infix epression and converts it
to a prefix expression, and should output the converted expression.
First, study the completed method, convert(..), which converts the expression from infix to prefix.
Second, study the incomplete main method. The main method should read a string, representing the infix expression, from standard out put. Note that the quotes are used to delineate a single string with embedded spaces, parenthesis, and other characters that are typically part of a single word. Note that InfixToPrefix does have an explicit private fields
Now you are ready to finish InfixToPrefix and convert expressions. First add comments to the top the file identifying partner A and B below the comments identifying the file. Again, you are expected to thoroughly debug your implementation and write your debugging code in the main method. Note that inExp.txt is an example infix expression, and you can use it for debugging. Leave all your code in place.
When time is called partner B should submit the completed files. Before submitting the file, please edit the files accordingly.
1. Be sure that all the code and comments from the previous partnerships are in the same file, InfixToPrefix.java, a
2. Delete the redundant import java.io.* statements, leaving only the statement at the top of the file.
3. Delete the public attribute from the SNodeList and ListStack classes so that only InfixToPrefix is the only public class.
The file InfixToPrefix.java should compile and run.
Now submit the edited file InfixToPrefix.java to cs2321, secGlab or secIlab, lab1, where secGlab is for students participating in a group labs and secIlab is for students participating in a individual labs.
After finishing the lab you must individually complete a short survey to receive full credit for the lab, links to the surveys are found on the course home page.