Contents
COSC 2436 – LAB4
TITLE ………………………………………………………………………………………………………………………………………….. 1 TIME TO COMPLETE …………………………………………………………………………………………………………………….. 1 COURSE OBJECTIVES – LEARNING OUTCOME …………………………………………………………………………………. 1 LAB OBJECTIVES ………………………………………………………………………………………………………………………….. 2 SKILLS REQUIRED…………………………………………………………………………………………………………………………. 2 HOW TO DO EACH PART ………………………………………………………………………………………………………………. 2 REQUIREMENT ……………………………………………………………………………………………………………………………. 3
LAB4 PART1 …………………………………………………………………………………………………………………………….. 3
LAB4 PART2 …………………………………………………………………………………………………………………………….. 4 HOW TO TURN IN THE LAB …………………………………………………………………………………………………………… 6 HOW TO GRADE THE LAB……………………………………………………………………………………………………………… 6
Note: in the instruction of the lab change “yourLastName” to your last name. In the example, change Smith to your last name, change James Smith to your full name, change Mary 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 -Evaluating 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 interface and apply polymorphism to the real life problem project
[LO3]
Describe and implement operations of Stack and Queue structures. Using Stack/Queue to the real life problem project
LAB OBJECTIVES
-Complete the lab on time (Time Management) -Can write the pseudo-code
-Can provide UML of data type class
-Can write comments in the program
-Can write the code of data type classes including data members, no-argument constructor, parameter constructors, mutator methods, assessor methods, method toString and other methods
-Can apply Inheritance concept to write the code of child classes 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 organize 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 Queue
-Can implement push/enqueue nodes, peek, pop/dequeue and show all nodes with Stack/Queue
SKILLS REQUIRED
To to this lab, students should review all the concepts required from the previous lab and add the following skills: -Learn how to create the data structure of type Stack and of type Queue
-Learn the algorithms of the operations, push and pop of Stack – enque and deque of Queue to see how the process work. Also, learn how to access these operation to insert, remove the node
-Learn how 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 write the generic code and apply to write the code for a generic stack -Learn how to declare an object of a generice class with specific 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 lab3 for class Account, CheckingAccount and SavingAccount
-Read the requirement of each part; write the pseudo-code in a word document by listing the step by step what you suppose to do in main() and then save it with the name as Lab4_pseudoCode_yourLastName
*Step2:
-start editor eClipse, create the project→project name:
FA2019_LAB4PART1_yourLastName(part1) OR FA2019_LAB4PART2_yourLastName (part2) -add data type classes (You can use these classes from lab3)
Account_yourLastName.java CheckingAccount_yourLastName.java SavingAccount_yourLastName.java
-Add data structure class:
Stack_yourLastName and Queue_yourLastName (part 1) GenericStack_yourLastName (part2)
-Add the driver class
FA2019_RestrictedStructureDemo_yourLastName (part1) FA2019_EvaluatingInfixedExpression_yourLastName (part2)
*Step3: Write the code of classes:
Re-use the code of data type classes from lab3
Write the code of Stack_yourLastName and Queue_yourLastName (Part1) -using the code on the page 140
And page 160 in the text book for your reference
Write the code of GenericStack_yourLastName (part2) – Using the code on the page 165 in the text book
for your referece with the following notices: Line 8: data = new T [100];
Line13: data = new T [n];
Line20: data[top] = newNode; (just for this lab)
Based on the pseudo-code write the java code of main() of the driver class FA2019_RestrictedStructureDemo_yourLastName (part1) or FA2019_EvaluatingInfixedExpression_yourLastName (part2)
*Step4: compile and run the program
*Step5: debug if there is any errors to complete the program
REQUIREMENT
LAB4 PART1
DATA TYPE CLASSES:
Using the data type classes from lab3:
-class Account_yourLastName
-class CheckingAccount_yourLastName
-class SavingAccount_yourLastName
Using the code on the page from the text book for your reference to produce the class Stack_yourLastName and Queue_yourLastName. Add the code of the following method to Stack_yourLastName or Queue_yourLastName
//This method should be added to Stack_yourLastName public Account_Smith 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 select types of data structure:
FA2019_RestrictedStructureDemo_Smith_Smith.java MAIN MENU
- Stack Structure
- Queue Structure
0. Exit
FOR EACH TYPE 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 CheckingAccount or SavingAccout For each one, insert the account to the data structure.
If Insert successfully display the message “Insert Account success”
Otherwise: display the message: “Insert Accout failed”
DELETE 1 NODE
Remove the node at the top (Stack) or at the front (Queue)
If the node exists, display the information of the node; otherwise display the message: “There is no account in the data structure”
DISPLAY THE NODE AT THE TOP (Stack) / AT THE FRONT (Queue)
Display the node at the top (Stack) or at the front (Queue)
If the node exists, display the information of the node, otherwise display the message: “Stack is empty” or “Queue is empty”
SHOW ALL NODES
Display all the accounts currently stored in the data structure
You should re-display the menu to allow users to continue using your program until they want to exit
LAB4 PART2
Create an application that can help users to evaluate the infixed expression
First, display the menu to allow users select the method where to read the input expression:
FA2019_EvaluatingInfixedExpression_Smith.java MENU TO SELECT WHERE TO READ INPUT
1. Read one Expression from the keyboard
2. Read expressions from an input file
0. Exit
CASE 1: //input from the keyboard
Reading one expression from the keyboard as a string
Do the following algorithm for one expression that include: create 2 stacks, split the expression into tokens, phase 1, phase 2 and display the result:
CREATE TWO STACKS: stackForOperands is for storing the operands (Integer) and stackForOperators is for storing operators (Character)
SPLIT THE EXPRESSION INTO TOKENS
-Using StringTokenizer to split the string of expression into the tokens (either they are operands or operators)
PHASE1: Read each token of the expression from left to right and store them to stack of operands (numbers) and stack of 6 operators: + – * / ( ) by applying the following rules:
- if the token is a NUMBER, push it to the stackForOperands
- if the token is AN OPEN PARENTHESIS ”(“, push it to the stackForOperators
- 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 stackForOperators:
–if the top is one of 4 operator + – * / then call the method processOfOneOperator() –If at the top of stackForOpertors there is nothing
or something not one of 4 operators + – * / then push it in
- if the token is one of 2 operators * or /, do the following: Check the top of stackForOperators:
–if the top is one of 2 operator * / then call the method processOfOneOperator() –If at the top of stackForOpertors there is nothing
or something not one of 2 operators * / then push it in
PHASE 2: CLEARING THE stackForOperators
Create the loop to call the method processOfOneOperator() until stackForOperators is empty
DISPLAY THE RESULT FOR THE INPUT FROM THE KEYBOARD
• The format of the output result as below, the expression is the input string and the result is the last number that is popped from the stackForOperands
Expression = result
For example the output 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 each line of file as an input string that is one expression
For each expression: Do the following 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 keyboard
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 from the stackForOperands
Expression = result
For example the output of the file expresions.txt as below: (file expressions.txt is downloaded from eCampus)
FA2019_EvaluatingInfixedExpression_Smith.java EXPRESSION FROM THE INPUT FILE expressions.txt 23 + 28 = 51
64 * 25 = 1600
14 + 25 – 12 = 27
36 * 14 / 42 = 12
25 + (12 + 34 * 23) = 819 (25+63–12)*20–(8*12) = 1424
HOW TO TURN IN THE LAB
Part 1: (you can zip whole 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 whole part 2 folder into one zip file to submit part 2 Pseudo-code of part 2
GenericStack_yourLastName.java FA2019_EvaluatingInfixedExpression_yourLastName.java
GenericStack_yourLastName.class FA2019_EvaluatingInfixedExpression_yourLastName.class
HOW TO GRADE THE LAB