Contents COSC 2436 – LAB4 TITLE .............................................................................................................................................................. 1 TIME TO

COSC 243 6 – LAB 4 Contents TITLE ................................ ................................ ................................ ................................ .............................. 1 TIME TO COMPLETE ................................ ................................ ................................ ................................ ...... 1 COURSE OBJECTIVES – LEARNING OUTCOME ................................ ................................ .............................. 1 LAB OBJECTIVES ................................ ................................ ................................ ................................ ............ 2 SKILLS REQUIRED ................................ ................................ ................................ ................................ ........... 2 HOW TO DO EACH PART ................................ ................................ ................................ ............................... 2 REQUIREMEN T ................................ ................................ ................................ ................................ .............. 3 LAB4 PART1 ................................ ................................ ................................ ................................ ............... 3 LAB4 PART2 ................................ ................................ ................................ ................................ ............... 4 HOW TO TURN IN THE LAB ................................ ................................ ................................ ........................... 6 HOW TO GRADE T HE LAB ................................ ................................ ................................ .............................. 6 Note: in the instruction of the lab change “yourLastName” to your last name . In the example, change Smith to your last name, ch ange J ames Smith to your full name, change Mar y Lane to the name that users type in from the keyboard (if these words are in this instruction) TITLE Restricted Data Structure: Stack and Queue -Evaluat ing the infixed Math expression TIME TO COMPLETE Two week COURSE OBJECTIVES – LEARNING OUTCOME [LO1] Provide UML class diagram and the code of data type classes Provide the pseudo -code or flowchart based on the requirement of a project before writing the code of the driver class. Also, can access data members of data type classes Describe and implement the inheritance relationship between super class and child classes. Can use abstract classes or interf ace and apply polymorphism to the real life problem proje ct [LO3] Describe and implement operations of Stack and Queue structures. Using Stack/Queue to the real life problem project LAB OBJECTIVES -Co mplete the lab on time (Time Management) -Can w rite the pseudo -code -Can pr ovide UML of data type class -Can w rite comments in the program -Can w rite the code of data type classes including data members, no -argument constructor, parameter constructors, mutator methods, assessor methods, method toString and ot her methods -Can apply Inheritance concept to w rite the code of child class es that inherits data members, constructors and other methods from parent class -Can apply Polymorphism: using object of the parent class to point to object of child classes -Can org anize the program with selection control structure: if..else, switch, do..while -Can create object and can access members of data type class -Can create the data structure type of Stack and Que ue -Can implement push/enqueue nodes, peek, pop/dequeue and show all nodes with Stack /Queue SKILLS REQUIRED To to this lab, student s sho uld review all the concepts required from the previ ous lab and add the following skills: -Learn how to create the data structure of ty pe Stack and of type Queue -Learn the alg orithm s of the operations, push and pop of Stack – enq ue and deque of Queue to see how the pro cess work . Also , learn how to access these oper ation to inser t, remove the node -Learn h ow to fetch the node from Stack and Queue by writing the method peek() -Learn how to show all the nodes in the Stack or Queue by writing the method showAll() -Learn how to writ e the generic code and apply to write the code for a generic stack -Learn how to declare an object of a generice class with s pecific data type HOW TO DO EACH PART From now and on yourLastName will be changed to your last name *Step1 : -Create UML of data type classes: reuse from lab 3 for class Account, CheckingAccount and SavingAccount -Read the requirement of each part; write the pseudo -code in a word do cument by listing the step by step what you suppose to do in main() and then save it with the name as Lab 4_pseudoCode_yourLastName *Step2 : -start editor eClipse, create the project → project name: FA2019_LAB 4PART1 _yourLa stName (part 1) OR FA2019_LAB 4PART2_yourLastName (part2) -add data t ype class es (You can use these classes from lab 3) Account_yourLastName .java CheckingAccount _yourLastName.java SavingAccount_yourLastName.java -Add data structure class : Stack _yourLastName and Queue_yourLastName (part 1) GenericSt ack_yourLastN ame (part2) -Add the driver class FA2019_ Restric ted StructureDemo_yourLastName (part1) FA2019_ Evaluating InfixedExpression _yourLastName (part 2) *Step3 : Write the code of classes: Re-use the code of data type classes from lab 3 Write the code of Stack_ yourLastName and Queue_yourLastN ame ( Part1 ) -using the co de on the p age 140 And page 160 in the text book for your reference Write the code of G enericStack_yourLastName (part2) – Using the code on the page 165 in the text book for your referece with the follo wing notices: Line 8: data = new T [100]; Line 13: data = new T [ n]; Line 20: data [top] = newNode ; (just for this lab) Based on the pseudo -code write the java code of main() of the d river class FA2019_RestrictedStructureDemo _yourLastName (part1) or FA2019_EvaluatingInfixedExpression _yourLast Name (part2) *Step4: compile and run the program *Step5 : d ebug if there is any errors to complete the program REQUIREMENT LAB4 PART1 DATA TYPE CLA SSES: Using the data type classes from lab 3: -class Account_yourLastName -class CheckingAccount_yourLastName -class SavingAccount_yourLastName Using the co de on the p age from the text book for your reference to prod uce the class Stack_yourLastName and Queue_yourLastName . Add the code of the following method to Stack_yourLast Name or Queue_yourLastName //Thi s method should be added to Stack _yourLastName public Account_S mith peek() { if (top != -1) { return data[top].deepCopy(); } return null; } //This method should be added to Queue_yourLastName public Account_Smith peek() { If (numberOfNode !=0) { return data[front].deepCopy(); } return null; } DRIVER CLASS Provide the pseudo -code or flowchart then write the code for the application FA2019_RestrictedStructureDemo _yourLastName that first display the following menu to sel ect types of data structure: FA2019_RestrictedStructureDemo _Smith _Smith .java MAIN MENU 1. Stack Structure 2. Queue Struct ure 0. Exit FOR EACH TYP E OF RESTRICTED STRUCTURE DO THE FOLLOWING TASKS SEQUENTIALLY: INSERT 3 NODES TO THE STRUCTURE Ask for the information and read from the keyboard for either Che ckingAccount or SavingAccout For each o ne, i nsert the account to the data structure. If Insert s ucc essfully dis play the message “Insert Account success ” Otherwise: display the message: “Insert A ccout failed ” DELETE 1 NO DE Remove the node at the top (Stack) or at the front (Queue) If the node exists , display the information of the node ; otherw ise dis play the message: “There is no account in the data structure ” DISPLAY THE NODE AT THE TOP (Stack) / AT THE FRONT (Q ueue) Display the node at the top (Stack) or at the front (Queue) If the node exists, disp lay the information of the node, otherwise display the message: “Sta ck is empty ” or “Queue is empty ” SHOW ALL NODES Display all the ac counts curren tly stored in the data structure You should re-display the me nu to allow users to co ntinue using y our program until they want to exit LAB4 PART2 Creat e an application th at can help users to evaluate the infixed e xpression First, display the menu to allow users select the method where to read the input e xpression: FA2019_EvaluatingInfixedExpression _Smith.java MENU TO SEL ECT WHERE TO READ INPUT 1. Read o ne Expression from the keyboard 2. Read e xpressions from an input fil e 0. Exit CASE 1 : //input from the keybo ard Reading one expression from the keyboard as a string Do the f ollowing algorithm for one expression that include : create 2 stacks, split the expression into tokens , phase 1, phase 2 and display the result : CRE ATE TWO STACKS : stackForOperands is for s toring the ope rands (Integer) and stackForOperators is for storing operators (Charact er) SPLIT T HE EXPRESSION INTO TOKENS -Using StringTokenizer to split the s tring of expression into the tokens (either they are operands or operators) PHASE 1: Read each toke n of the expression from left to right and store them to stack of operands (numbers) and stac k of 6 operators : + - * / ( ) by applyin g the following rules: • if the token is a NUMBER , push it to the stackForOperands • if the toke n is AN OPEN PARENTHESI S ”(“, push it to the stack ForOperators • if the token is AN CLOSE PARENTHESIS “)”, do the following: Create a loop , access the method processOfOneOperator() until the top of stackForOperators is the OPEN PARENTHESIS “(”, pop it off • if the token is one of 2 operators + or – , do the following: Check the top of stackFor Operators : --if the top is one of 4 operator + - * / then call the method process OfOne Operator() --If at the top of stackForOpertors there is nothing or something not one of 4 op erator s + - * / then pus h it in • if the token is one of 2 operator s * or / , do the following: Check the top of stackFor Operators : --if the top is one of 2 operator * / then call the method process OfOne Operator() --If at the top of stackForOpertors ther e is nothing or something not one of 2 op erator s * / then pus h it in PHASE 2: C LEARING THE stackForOp erators  Create the loop to call the method p rocess OfOneOperator() until stack ForOperators is empty DISPLAY THE RESULT FOR THE INPUT FROM THE KEYBO ARD • The format of the output result as below , the expression is the input string and the result is the last number that is popped f rom the st ackForOperands Express ion = result For e xample the out put of the expresion (25 + 63 – 12) * 20 – (8 * 12) is: FA2019_EvaluatingInfixedExpression _Smith.java EXPRESSION FROM THE KEYBOARD (25 + 63 – 12) * 20 – (8 * 12) = 1424 CASE 2: //Input from the file Read file name Open input file Loop to read the file Read e ach line of file as an input string that is one expre ssion For each expression : Do the f ollowing algorithm that include : create 2 stacks, split the expression into tokens , phase 1, phase 2 and display the result as you did for one expression that is read from the key board DISPLAY THE RESULT FOR THE INPUT FROM THE FILE • The format of the output result as below , the expression is the input string and the result is the last number that is popped f rom the st ackForOperands Express ion = result For e xample the out put of the file expresion s.txt as below: (file expre ssions.txt is downloaded from e Campus ) FA2019_EvaluatingInfixedExpression _Smith.java EXPRESSION FROM THE INPUT FILE expre ssions.txt 23 + 28 = 51 64 * 25 = 1 600 14 + 25 – 12 = 27 36 * 1 4 / 42 = 12 25 + (12 + 34 * 23) = 819 (25 + 63 – 12) * 20 – (8 * 12) = 1424 HOW TO TU RN IN THE LAB Part 1: (you can zip who le part 1 folder into one .zip file to submit part1) Pseudo -code of part 1 Account_yourLastName .java CheckingAccount_yourLastName .java SavingAccount_yourLastName .java Stack_yourLastName .java Queue_yourLastName .java FA2019_RestrictedStructureDemo _yourLastName .java Account_yourLastName .class CheckingAccount_yourLastName .class SavingAccount_yourLastName .class Stack_yourLastName .class Queue_yourLastName .class FA2019_RestrictedStructureDemo _yourLastName .class Part2: (you can zip wh ole part 2 folder into one zip file to submit part 2 Pseudo -code of part 2 Generi cStack_y ourLastName .java FA2019_ Evaluat ingInfixedExpression_yourLastName .java Generi cStack_y ourLastName .class FA2019_ Evaluat ingInfixedExpression_yourLastName .class HOW TO GRADE THE LAB