Project 2: Linked Stacks Solution

Project 2: Linked Stacks Homework projects should be worked on by each individual student. Brainstorming and sketching out problems on paper or on a whiteboard together are permitted, but do not copy code from someone else or allow your code to be copied. Students who commit or aid in plagiarism will receive a 0% on the assignment and be reported.













Information




Topics: Linked structures, stacks, exceptions




Turn in: Turn in all source les - .cpp, .hpp, and/or .h les. Do not turn in Visual Studio les.




Starter les: Download from GitHub.




Building and running: If you are using Visual Studio, make sure to run with debugging. (Don't run without debugging!) Using the debugger will help you nd errors.




To prevent a program exit, use this before return 0;




cin.ignore();




cin.get();




Tips:




Always make sure it builds. Only add a few lines of code at a time and build after each small change to ensure your program still builds.




One feature at a time. Only implement one feature (or one function) at a time. Make sure it builds, runs, and works as intended before moving on to the next feature.




Search for build errors. Chances are someone else has had the same build error before. Copy the message into a search engine and look for information on why it occurs, and how to resolve it.




Use debug tools, such as breakpoints, stack trace, and variable watch.




Don't implement everything in one go. Don't just try typing out all the code in one go without building, running, and testing. It will be much harder to debug if you've tried to program everything all at once.









Contents



















1
Getting started
3


1.1
About . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3




1.1.1
Program purpose . . . . . . . . . . . . . . . . . . . . .
3




1.1.2
Project les . . . . . . . . . . . . . . . . . . . . . . . .
4




1.1.3
Path issues . . . . . . . . . . . . . . . . . . . . . . . .
5




1.1.4
Tester . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2
Lab speci cations
7


2.1
Creating the CourseNotFound exception . . . . . . . . . . . .
7


2.2
Writing the LinkedStack . . . . . . . . . . . . . . . . . . . . .
8




2.2.1
Stack functionality . . . . . . . . . . . . . . . . . . . .
9




2.2.2
Testing . . . . . . . . . . . . . . . . . . . . . . . . . . .
10


2.3
Implementing the prereq functionality . . . . . . . . . . . . . .
11




2.3.1
void ViewCourses() . . . . . . . . . . . . . . . . . . . .
11




2.3.2
Course FindCourse( const string& code ) . . . . . . . .
11




2.3.3
void ViewPrereqs() . . . . . . . . . . . . . . . . . . . .
12
3
Example output
14
4
Grading breakdown
17


PART 1







Getting started
















About




Program purpose




This program loads in a list of courses from the courses.txt le. This text le contains a list of classes: their codes and names, and one prerequisite. You won't have to write the le reader; that has been implemented for you.




COURSE
MATH111
F u n d a m e n t a l s _ o f _ M a t h e m a t i c s
COURSE
MATH115
E l e m e n t a r y _ A l g e b r a
PREREQ
MATH111


COURSE
MATH116
I n t e r m e d i a t e _ A l g e b r a
PREREQ
MATH115


COURSE
MATH173
P r e c a l c u l u s
PREREQ
MATH116














Figure 1.1: Part of the input text le




In the program, the user can view a list of all classes, or view prerequisites for a given class. All classes will be stored in a LinkedList, and your Stack will be used to collect lists of prerequisites, until you hit a course that does not have any prerequisites.




You can use the LinkedList as reference while you're implementing the Stack.







CS 250,
Project 2: Linked Stacks


























- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -








|
GET PREREQS |










- - - - - - - - - - - - - - -






















Enter class code











CS250












Classes to
take :


























1.
CS134
P r o g r a m m i n g _ F u n d a m e n t a l s










2.
CS200
C o n c e p t s _ o f _ P r o g r a m m i n g _ A l g o r i t h m s _ U s i n g _ C ++








3.
CS235
O b j e c t _ O r i e n t e d _ P r o g r a m m i n g _ U s i n g _ C ++








4.
CS250
B a s i c _ D a t a _ S t r u c t u r e s _ U s i n g _ C ++























Figure 1.2: The program showing a list of prerequisites







Project les




The project contains the following les. You will be modifying the les marked with *.










Project 2 - Stacks/




CUTEST/




StringUtil.hpp ... Tester files




TesterBase.hpp ... Tester files




TesterBase.cpp ... Tester files




DATA STRUCTURES/







Node.hpp ... The Node used by List and Stack LinkedList.hpp ... Linked List (already written)




LinkedStack.hpp ... Linked Stack



EXCEPTIONS/




CourseNotFoundException.hpp ...



Custom exception







UTILITIES/




Menu.hpp ... Menu utility for program Course.hpp ... The Course struct CourseCatalog.hpp ... Header for the main program Tester.cpp







* CourseCatalog.cpp ... Implementation for the main program




prereq finder.hpp ... Contains main()











courses.txt ... Input text file













Path issues




You will need to take notice of where test results.html gets written to, and where courses.txt is read from. It will be the same path on your machine, but where it should be on your machine depends on the IDE you're using.




When you run the program, it should try to tell you the proper path:




* TEST LOG WILL
BE WRITTEN OUT
TO :










[...]/ Projects
2018 -01/ Project
2 -
Stacks / Project2 - Stacks
student

















Figure 1.3: The program trying to display the program's running directory










Tester




Tests are already written in this project. It uses Rachel's cuTEST framework. The tests will run when you launch the program, and there will be some basic output to the console window with an overview of tests being run and what passes/fails. For more information on the tests, make sure to open the test results.html le.





































Figure 1.4: The test output.




The test output will contain information for each test, including:




The test name and description of the test List of prerequisite functions





Whether it passed or failed Expected and actual values




Suggestions on what to check to x





PART 2







Lab speci cations
















Creating the CourseNotFound exception




Before you implement the Stack, you should have the CourseNotFound cus-tom exception written. If the user tries to access the Top() item from the Stack, but the Stack is empty, then this exception will be thrown.




In EXCEPTIONS/CourseNotFoundException.hpp, you'll create a class named CourseNotFound, which inherits from the runtime error exception. All you need here is a constructor that takes in a string parameter for the error, and then call the runtime error's constructor with that information.







class C o u r s e N o t F o u n d : public r u n t i m e _ e r r o r



2 {




3
public :


4
C o u r s e N o t F o u n d ( const
string & error )
5
: r u n t i m e _ e r r o r ( error )
6
{


7
// Nothing to do
here
8




}


9
};














Figure 2.1: Code for the CourseNotFound exception

Writing the LinkedStack













m ptrLast







Top

























Bottom




m ptrFirst










Within the DATA STRUCTURES/Stack.hpp le, you will be implementing a LinkedStack. This means, like a LinkedList, it will use Node pointers, instead of being implemented with an array.







You can use the LinkedList either as reference, or as a parent for the LinkedStack as you're implementing it.




Stack functionality




Push




As you add items to the stack, it lls from bottom-up. Push will not throw any exceptions.







ptrFirst NULL




ptrLast NULL














ptrLast
























ptrFirst










B
































A
ptrFirst
















A












ptrLast




















































Empty
Add \A"


Add \B"





























Pop




Pop removes the top-most item from the stack. Pop will not throw any exceptions. If Pop is called on an empty Stack, nothing occurs.







ptrLast






















Z
ptrLast
















































Y


Y
ptrFirst


































ptrFirst






ptrFirst




X




X


X














ptrLast
















































Has 3 items


Pop() removes \Z"
Pop() removes \Y"




Top




Top returns the value of the top-most item of the stack. Top will throw a CourseNotFound exception if the stack is empty when Top() is called.



















ptrFirst


NULL














ptrLast










ptrLast


NULL


































3
ptrLast


























































d














2


































c




















































ptrFirst








b












1
















ptrFirst


a
































































Top() returns \3"
Top() returns \d"
Top() throws exception


















Testing




As you write the functionality for the stack, make sure to run the tests to validate your work. Once all tests pass, you should be able to move on to implementing the main program's functionality.











Implementing the prereq functionality




The program's main functionality is held in the CourseCatalog les. Make sure to mark functions that don't throw exceptions as noexcept .




void ViewCourses()




This function will not throw any exceptions.




Use the LinkedList's Size() and operator[] functions to access each course in the list in a for-loop. Display each course's code, name, and pre-requisite.







- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




| VIEW COURSES |




- - - - - - - - - - - - - - - -







# CODE TITLE




PREREQS




- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




0
MATH111
F u n d a m e n t a l s _ o f _ M a t h e m a t i c s
1
MATH115
E l e m e n t a r y _ A l g e b r a


MATH111


2
MATH116
I n t e r m e d i a t e _ A l g e b r a


MATH115








3
MATH173
P r e c a l c u l u s


MATH116














Figure 2.2: A partial view of the class output



















Course FindCourse( const string& code )




This function takes in a course code, such as \CS250", \MATH171", etc. It will search through the m courses LinkedList, and if found, it will return that course.




Otherwise, it will throw the CourseNotFound exception.








void ViewPrereqs()




This function will not throw any exceptions.




First, you need to get the course code from the user.




Use the FindCourse function to get that course.




current = FindCourse( courseCode );




Make sure to wrap it in a try/catch! If the CourseNotFound exception is caught, then display an error message and leave the ViewPrereqs function.







- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




| GET PREREQS |




- - - - - - - - - - - - - - -







Enter class code







CS123







Error ! Unable to find course CS123 !







Figure 2.3: Unable to nd a course by its code




After the course has been found, create a Stack of Courses




LinkedStack<Course prereqs;




and push the current course that you've found.




Then, create a while loop. We will keep re-using the current Course object, storing each prerequisite, until we run out. So, for the loop, continue looping while current.prereq != "".




Within the loop, use FindCourse again to nd the current course's pre-requisite. Surround this in a try/catch!




If the course isn't found, then break out of the while loop.




Otherwise, if the course is found, then push it onto the prereqs stack.




The loop will stop once we've run out of prerequisites. At this point, the stack should be full of classes, with the class the user selected at the bottom, and each prereq, in order, until we get to the top.








Finally, we're going to display all the classes to the user. Create another while loop. This one will keep looping while the prereqs stack is not empty.




Within the loop, get the top course from the stack. Display its code and name. Then, pop it o the stack.




The while loop should end once the stack is empty.







- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




| GET PREREQS |




- - - - - - - - - - - - - - -







Enter class code







MATH254







Classes to take :




1. MATH111 F u n d a m e n t a l s _ o f _ M a t h e m a t i c s




2. MATH115 E l e m e n t a r y _ A l g e b r a




3. MATH116 I n t e r m e d i a t e _ A l g e b r a




MATH173 P r e c a l c u l u s



5. MATH241 C a l c u l u s _ I




6. MATH242 C a l c u l u s _ I I




7. MATH243 C a l c u l u s _ I I I




8. MATH254 D i f f e r e n t i a l _ E q u a t i o n s







Figure 2.4: Getting prereqs for MATH254





PART 3







Example output






















- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




|
Running
tests ...
|
- - - - - - - - - - - - - - - - - - - -
*
TEST LOG
WILL BE
WRITTEN OUT TO :











/ home / r ay ec he ll / TEACHING / cs250 / cs -250 - private - files / Projects




2018 -01/ Project
2 - Stacks / Project2 - Stacks SOLUTION
Running testset
1 out of 1:
T e s t _ S t a c k ()
* Create an empty
Stack , make sure Size () is 0.


...
PASS






* Create a Stack .
Push 5. Size () should be 1. Top () should
be 5.
...
FAIL













*
Create
a Stack . Push 'A ' & 'B '. Size () should be 2. Check


order .
...
FAIL
*
Create
a Stack . Push 3 items and Pop . Check Size () . Check


Top () .
...
FAIL





























NOTE : CHECK " t e s t _ r e s u l t . html " FOR FULL DETAILS .







- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




| LOADING COURSES |




- - - - - - - - - - - - - - - - - - -







* 17 courses loaded







Figure 3.1: Program starts and runs tests





- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




| MAIN MENU |




- - - - - - - - - - - - -







1. View all courses




2. Get course p r e r e q u i s i t e s




3. Exit







2







Figure 3.2: Main menu
















- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




| GET PREREQS |




- - - - - - - - - - - - - - -







Enter class code







CS250







Classes to take :




1. CS134 P r o g r a m m i n g _ F u n d a m e n t a l s




2. CS200 C o n c e p t s _ o f _ P r o g r a m m i n g _ A l g o r i t h m s _ U s i n g _ C ++




3. CS235 O b j e c t _ O r i e n t e d _ P r o g r a m m i n g _ U s i n g _ C ++




4. CS250 B a s i c _ D a t a _ S t r u c t u r e s _ U s i n g _ C ++







Figure 3.3: Getting prereqs for CS250
















- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




| GET PREREQS |




- - - - - - - - - - - - - - -







Enter class code







CS123







Error ! Unable to find course CS123 !







Figure 3.4: Unable to nd a course by its code











- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




|
VIEW COURSES
|
- - - - - - - - - - - - - - - -






#
CODE
TITLE


PREREQS


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
0
MATH111
F u n d a m e n t a l s _ o f _ M a t h e m a t i c s
1
MATH115
E l e m e n t a r y _ A l g e b r a








MATH111


2
MATH116
I n t e r m e d i a t e _ A l g e b r a


MATH115


3
MATH173
P r e c a l c u l u s


MATH116


4
MATH241
C a l c u l u s _ I








MATH173


5
MATH242
C a l c u l u s _ I I


MATH241


6
MATH243
C a l c u l u s _ I I I


MATH242


7
MATH254
D i f f e r e n t i a l _ E q u a t i o n s








MATH243


8
CS134
P r o g r a m m i n g _ F u n d a m e n t a l s
9
CS200
C o n c e p t s _ o f _ P r o g r a m m i n g _ A l g o r i t h m s _ U s i n g _ C ++


CS134


10
CS210
D i s c r e t e _ S t r u c t u r e s _ I


MATH171








11
CS211
D i s c r e t e _ S t r u c t u r e s _ I I


CS210


12
CS235
O b j e c t _ O r i e n t e d _ P r o g r a m m i n g _ U s i n g _ C ++


CS200


13
CS250
B a s i c _ D a t a _ S t r u c t u r e s _ U s i n g _ C ++


CS235








14
FL165
E l e m e n t a r y _ C h i n e s e _ I
15
FL166
E l e m e n t a r y _ C h i n e s e _ I I


FL165


16
FL192
I n t e r m e d i a t e _ C h i n e s e _ I


FL166

















Press ENTER to continue ...







Figure 3.5: Viewing all courses