c++ program Given this question and my code( done using a linked list) could you
ID: 3762841 • Letter: C
Question
c++ program
Given this question and my code( done using a linked list) could you change every instance of a linked list to an array
thanks!
executable code :
_______________
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ofstream output;
struct listNode{
string tags;
int occurences;
listNode *nextNode;
listNode *prevNode;
}*tempLoc, *previous, *current, *head,*head2, *headEven, *tail,*tail2, *tailEven;
//NUMBER 1
listNode addToList(string tagToLL)
{
tempLoc = new listNode;
tempLoc->tags = tagToLL;
tempLoc->occurences = 1;
tempLoc->nextNode = NULL;
tempLoc->prevNode = NULL;
current = NULL;
previous = NULL;
if (head == NULL)
{
head = tempLoc;
tail = tempLoc;
}
else
{
previous = head;
current = head->nextNode;
while (current != NULL)
{
previous = current;
current = current->nextNode;
}
previous->nextNode = tempLoc;
tempLoc->prevNode = previous;
tail = tempLoc;
}
return *head;
}
//NUMBER 3
void ToStack(string tagToLL)
{
tempLoc = new listNode;
tempLoc->tags = tagToLL;
tempLoc->occurences = 1;
tempLoc->nextNode = NULL;
tempLoc->prevNode = NULL;
current = NULL;
previous = NULL;
if (head2 == NULL)
{
head2 = tempLoc;
tail2 = tempLoc;
}
else
{
previous = head2;
current = head2->nextNode;
while (current != NULL)
{
previous = current;
current = current->nextNode;
};
previous->nextNode = tempLoc;
tempLoc->prevNode = previous;
tail2 = tempLoc;
// This function places ALL tags into list first
// Next it checks if the last 2 tags in list are matching tags of each other
if (tail2->tags.at(1) == '/')
{ // Erases that index at the 1 location which should be the '/' character
string match;
match = tail2->tags;
match.erase(match.begin()+1); // </tag>
// ^ deletes this character... new string looks like <tag>
// Using the new string to compare to starting tag
//Checking for matching tag if this is an ending tag
if (tail2->prevNode->tags == match)
{
if (tail2->prevNode->prevNode != NULL) // Checks if its last tag in list
{
tail2 = tail2->prevNode;
tail2->nextNode->prevNode = NULL;
delete tail2->nextNode;
tail2->nextNode = NULL;
tempLoc = NULL;
tail2 = tail2->prevNode;
delete tail2->nextNode;
tail2->nextNode = NULL;
}
else
{ // If tag had a match and all tags are deleted from stack
cout << "Input file has been read, results are showed below: " << endl << endl;
output << "Input file has been read, results are showed below: " << endl << endl;
tail2 = tail2->prevNode;
tail2->nextNode->prevNode = NULL;
delete tail2->nextNode;
tail2->nextNode = NULL;
delete tail2;
tempLoc = NULL;
head2 = NULL;
tail2 = NULL;
}
}
else
{
cout << "Error Message: Please check if " << tempLoc->tags << " is placed correctly" << endl;
output << "Error Message: Please check if " << tempLoc->tags << " is placed correctly" << endl;
tail2 = tail2->prevNode;
delete tail2->nextNode;
tail2->nextNode = NULL;
}
}
}
}
//NUMBER 5
void AlphabeticalList(string tagToLL){
if (tagToLL.at(1) != '/')
{
tempLoc = new listNode;
tempLoc->tags = tagToLL;
tempLoc->occurences = 1;
tempLoc->nextNode = NULL;
tempLoc->prevNode = NULL;
current = NULL;
previous = NULL;
if (head2 == NULL)
{
head2 = tempLoc;
tail2 = tempLoc;
}
else if (tempLoc->tags < head2->tags)
{
tempLoc->nextNode = head2;
head2->prevNode = tempLoc;
head2 = tempLoc;
}
else if (tempLoc->tags == head2->tags)
{
head2->occurences = head2->occurences + 1;
}
else if (tempLoc->tags > head2->tags)
{
previous = head2;
current = head2->nextNode;
while (current != NULL && current->tags < tempLoc->tags)
{
previous = current;
current = current->nextNode;
}
if (current == NULL)
{
previous->nextNode = tempLoc;
tempLoc->prevNode = previous;
tail2 = tempLoc;
}
else if (current->tags == tempLoc->tags)
{
current->occurences = current->occurences + 1;
}
else if (current->tags > tempLoc->tags)
{
current->prevNode->nextNode = tempLoc;
tempLoc->prevNode = current->prevNode;
tempLoc->nextNode = current;
current->prevNode = tempLoc;
}
}
}
}
int main()
{
output.open("output.txt");
output << "output Log: " << endl << endl;
string line, tagToLL;
ifstream myfile("input1.txt");
if (myfile.is_open())
{
while (getline(myfile, line))
{
for (int i = 0; i < line.length(); i++)
{
if (line.at(i) == '<')
{
int endofLine = i;
while (line.at(endofLine) != '>')
{
endofLine = endofLine + 1;
}
tagToLL = line.substr(i, endofLine + 1);
if (tagToLL == "<P>" || tagToLL == "<BR>" || tagToLL.substr(1, 3) == "IMG")
{
addToList(tagToLL);
}
else
{
ToStack(tagToLL);
}
}
}
cout<<line<<endl;
}
}
else
{
cout << "Unable to open file"<<endl;
}
if (head2 != NULL)
{
cout <<" matching ending tags for These/This tag(s) do(es) not exist:" << endl;
output <<" matching ending tags for These/This tag(s) do(es) not exist:" << endl;
previous = head2;
current = head2->nextNode;
while (previous != NULL)
{
cout << previous->tags << endl;
output<< previous->tags << endl;
previous = current;
if (current != NULL)
current = current->nextNode;
}
cout << endl << "Make sure the tags are properly placed in the input file. " << endl;
output << endl << "Make sure the tags are properly placed in the input file. " << endl;
}
else {
cout << endl <<"All tags have matching closing tags"<< endl;
output << endl << "All tags have matching closing tags" << endl;
}
myfile.clear();
myfile.seekg(0); // Resets to beginning of file
// Placing tags into alphabetical list
head2 = NULL;
while (!myfile.eof())
{
getline(myfile, line);
for (int i = 0; i < line.length(); i++) // Checking whole line by each character
{
if (line.at(i) == '<') // Searches for index of where a tag starts
{
int endofLine = i;
while (line.at(endofLine) != '>') // Used to get index of where a tag ends
{
endofLine = endofLine + 1;
}
endofLine = endofLine + 1; // This is where the '>' index is located
tagToLL = line.substr(i, endofLine); // Creates the 'tag' string from the line by using first and last index
// to find the '<' and '>' operators and place all its content into new string
if (tagToLL != "<P>" && tagToLL != "<BR>" && tagToLL.substr(1, 3) != "IMG")
{ // Checks for tags other than <P>, <BR>, and <IMG...> tags
AlphabeticalList(tagToLL);
}
}
}
}
cout << endl;
cout << "Alphabetical list of tags in input file: " << endl<<endl;
output << endl;
output<< "Alphabetical list of tags in input file: " << endl<<endl;
previous = head2;
current = previous->nextNode;
while (previous != NULL)
{
cout << previous->tags << " - occurred " << previous->occurences << " time(s). " << endl;
output << previous->tags << " - occurred " << previous->occurences << " time(s). " << endl;
previous = current;
if (current != NULL)
current = current->nextNode;
}
myfile.close();
output.close();
return 0;
}
Explanation / Answer
The particular problem can be solved using stack which is Last In First Out (LIFO) structure. Using linked list for implementing stack makes it more flexible than arrays. As per your requirement the stack has to be implemented using arrays and to do so we must be knowing in advance the total number of elements the stack can hold. So lets put that number in a variable "max" and initialize it to 0 and another variable "top" will be used to keep track of the number of elements currently on the stack. To push an element on to the stack, first check if the stack is already full and if its not full then push an element onto stack and increment the top.
s[top++] = new_element;
Here is the code snippet
Now in your programme push each starting tag (tags not containing '/' at second place) on to the stack using push function and pop an element whenever an end tag is encountered using pop function.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.