Assignment 3 Stack

Submission

• In github, commit and push the final version of your code before the assignment deadline. You should get in the habit of pushing changes every time you get a new part of the assignment working.
• There is no writeup for the stack part of this assignment, so there will not be a submission in Canvas.

Overview

In this part of assignment 3, you will write a program that uses a stack to handle a parsing problem. The starter code includes the following files.

• Stack.h in which you will implement a LinkedList based stack

• htmlParse.cpp where you will implement the main function for the stack program

Assignment Requirements & Output

• You should use functions to make your main a manageable length and easy to understand.
• Implement functions as efficiently as reasonably possible. (Reasonable means you pick the optimal BigO based on learned structures.)
• Your code should not have memory leaks or other memory related errors. Check with valgrind
• You are not to use any library containers (vector/list) to implement your data structure. You can use utility functions like std::swap.
• Do not prompt for ANY input other than what is specified for in the descriptions below.

Output

Anything you are asked to print out should be printed in your final program with a clear label.

Label each section's output and print something like this before each section:

-----------------------------Section 1----------------------------
…

There should not be a lot of extra debugging output.

Grading

Your code will be built and tested from the command line. Your code must compile and run in that environment to receive credit.

You can get partial credit for code that is mostly there but broken. The maximum amount of credit awarded for each section will be:

• Code runs and provides correct output - full credit.
• Code runs and provides incorrect output - partial credit, potentially quite high.
• Code does not run or produce output (potentially because the program crashed in a previous section)- partial credit - generally less than incorrect output.
• Code that is commented out - partial credit. Less than incorrect output. If part of a program crashes but later parts work correctly, comment it out and leave a note in the output like "Part 4 disabled… causes crash" so I know to go check out what you did.
• Code that never runs because something before it crashed. Same as commented out code.

Part 0 - Setup

Begin by accepting the assignment repository listed in Canvas. Add this data file to the folder:

• Document.html (You may need to right-click the link and Save As to save the file instead of opening it.)

Do not check the sample document into source control. I will grade with my own version of the document. So while you can modify it to test your code, your code needs to work with the original version of the document.

Create a Makefile. When the make utility is executed in that folder, it should build an executable called program.exe. (You likely want to copy the .vscode folder, .clang-format, and Makefile from the Basic Project template into the folder as well.)

I will test your project by doing exactly this from your project directory:

make
./program.exe

Part 1

(25% of grade)

In Stack.h, implement a templated stack constructed with a singly linked list.

You should not modify the signature of existing functions that are declared, but can add additional ones. You must implement both print and reversePrint. You may skip implementing a copy constructor and/or assignment operator unless they are needed.

You are not to use any iteration in implementing Stack.h (no for/while/do…while). Any repetition must be done with recursion.

You will not be turning in any standalone tests of this part, but you will want to do some simple testing in main to verify this is working before getting too deep into part 2. (I have my own tests I will run it against.) Make sure Valgrind doesn't complain about memory issues.

Part 2

(20% of grade)

The file Document.html is a simplified HTML document where there are spaces between each token (piece of information). Each token is either:

• An HTML start tag : something that looks like <tag>. A tag always has < > around a word. It indicates the start of a new section of the document.
• An HTML end tag : something that looks like </tag>. An end tag always looks like </ > with a word in between. It indicates the end of a section. An end tag should always match the most recent start tag. (The current section must end before sections started even earlier may end).
• A plain word : something that looks like This

Modify HTMLParse.cpp's main function to read in the file Document.html.

Every time your program encounters a word, output it preceded by a list of the html tags it is nested inside. (Knowing what tags a word is inside would let us render it appropriately on a webpage.) For full credit, the tags should appear in order from oldest to newest like this:

<html> <body> <h3> My
<html> <body> <h3> webpage
<html> <body> <p> This
<html> <body> <p> is
<html> <body> <p> some
<html> <body> <p> <b> special
<html> <body> <p> text. 
<html> <body> <p> <i> <b> This
…

The logic for reading the document should be something like:

• <html> : A start tag. I am inside an <html>
• <body> :A start tag. I am inside a <body> which is inside an <html>
• <h3> : A start tag. I am inside an <h3> which is inside a <body> which is inside an <html>
• My : A word. Print it out with what it is inside.
• webpage : A word. Print it out with what it is inside.
• </h3> : An end tag. It correctly ends the <h3> I am inside. I am still inside a <body> which is inside an <html>
• ...

If your program detects a bad ending tag (one that does not match the current section), you should print out an error message and halt. If you finish reading the document without ending all the open tags of the document, you should report an error message. You will have to modify Document.html to test this! Deleting line 8 would make a bad ending tag (we then get to </body> without ever ending the <p>). Deleting the last line would make for a missing ending tag.