7
\$\begingroup\$

The exercise was to take a file such as this:

You say yes
I say no
You say stop
And I say go go go
CHORUS:
Oh no
You say Goodbye
And I say hello
Hello hello
I don't know why
You say Goodbye
I say hello
#repeat 9 12
Why
#repeat 11 13
I say high
You say low
You say why
And I say I don't know
#repeat 5 19

And parse the repeats so they actually repeat the lines. Nested repeats have to work and I had to use my own stack class.

main.cpp

#include "Stack.h"
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

void parseLines(const std::vector<std::string> text, const int begin, const int end);
void parseRepeat(const std::string repeatLine, int &begin, int &end);


int main() {
    int fileLines = 0;

    std::string in;
    std::string fileName = "lyrics";
    std::ifstream inFile(fileName.c_str());
    std::vector<std::string> text;

    while(!inFile.eof()) {
        getline(inFile, in);
        text.push_back(in);
        fileLines++;
    }

    parseLines(text, 0, fileLines);
}

void parseLines(const std::vector<std::string> text, const int begin, const int end) {
    Stack<int> lyricStack;

    int fromLine = begin;
    int toLine = end;


    while(fromLine <= toLine && (unsigned int)fromLine < text.size()) {
        if(text.at(fromLine).substr(0, 7) == "#repeat") {
            lyricStack.push(fromLine);
            lyricStack.push(toLine);

            parseRepeat(text.at(fromLine), fromLine, toLine);
        } else {
            std::cout << text.at(fromLine) << std::endl;
            fromLine++;
        }

    }


    while(!lyricStack.isEmpty()) {
        toLine = lyricStack.pop();
        fromLine = lyricStack.pop();

        fromLine++;

        parseLines(text, fromLine, toLine);
    }
}

void parseRepeat(const std::string repeatLine, int &begin, int &end) {
    std::string numbers = repeatLine.substr(repeatLine.find(" ") + 1);
    begin = atoi((numbers.substr(0, numbers.find(" "))).c_str()) - 1;
    end = atoi((numbers.substr(numbers.find(" "))).c_str()) - 1;
}

Stack.h

#ifndef STACK_H_
#define STACK_H_

#include <string>

template <class A>
struct NODE {
    A data;
    NODE* next;
};

template <class B>
class Stack {
private:
    NODE<B>* head;

public:
    Stack();
    virtual ~Stack();

    void push(const B item);
    B pop();
    bool isEmpty();
};

#endif /* STACK_H_ */

Stack.cpp

#include "Stack.h"
#include <string>

template <class B>
Stack<B>::Stack() {
    head = NULL;
}

template <class B>
Stack<B>::~Stack() {
    NODE<B>* current = head;
    NODE<B>* previous;

    while(current) {
        previous = current;
        current = current->next;
        delete previous;
    }
}

template <class B>
void Stack<B>::push(const B item) {
    NODE<B>* newNode = new NODE<B>;
    newNode->data = item;

    if(!head) {
        newNode->next = NULL;
        head = newNode;
    } else {
        newNode->next = head;
        head = newNode;
    }
}

template <class B>
B Stack<B>::pop() {
    NODE<B>* next = head->next;

    B data = head->data;

    delete head;

    head = next;

    return data;
}

template <class B>
bool Stack<B>::isEmpty() {
    if(!head) {
        return true;
    }

    return false;
}
\$\endgroup\$
12
\$\begingroup\$

First main problem is the code does not compile:

When you implement template classes. The compiler instantiates the templates on use. This means the compilation unit that is instantiating the class must have already seen the source for the template (if it has not then it marks it as unresolved) and then tries to resolve them at link time. In your case this does not happen.

main.cpp: Uses Stack<int> thus needs the constructor and destructor.
          But does not have them at this point. So waits for the linker to find one.

Stack.cpp: Contains only template definition and thus does **NOT** generate any code.
           Templates only become real code when there is an instantiation
           (implicit as done by the compiler in main.cpp or explicit when you do it).
           Since there is no instantiation there is no code.

This all means that main fill fail to link.

The easiest way to solve this:

  1. Rename Stack.cpp to Stack.tpp
  2. #include "Stack.tpp" from inside "Stack.h"

The reason to rename to Stack.tpp is that some build systems will try to build all source and since this is included by a header this can cause problems with some build systems. So it is best to change the name just to avoid any future problems. tpp is often used to hold template definitions.

Never do this:

while(!inFile.eof()) {
    getline(inFile, in);
    text.push_back(in);
    fileLines++;
}

Several problems:

  1. If getline() fails with a real error (not EOF) you end up with an infinite loop.
  2. The last line read reads up to (but not past the EOF).
    So you have read the last line but EOF is not set. You then re-enter the loop try to get another line, this fails and sets EOF but nothing is done with in yet you still push in onto text. So you end up pushing the last line twice.

The correct way to read from a file is:

while(getline(inFile, in))
{
    // The loop is only entered if getline() successfully reads a line.
    // Thus it solves the two problems above.

    text.push_back(in);
    fileLines++;
}

This works because getline() returns a reference to a stream. When a stream is used in a boolean context it is converted to a type that can be used as a boolean (type unspecified in C++03 but bool in C++11). It is converted by checking the fail() flag. If this is true the conversion returns an object equivalent to false otherwise an object equivalent to true.

When passing big objects as parameters consider passing them by reference. If they are never modified pass by const reference. If you don't the compiler is going to generate a copy.

void parseLines(const std::vector<std::string> text, const int begin, const int end) {

Here you should probably pass text by const reference.

void parseLines(const std::vector<std::string> const& text, const int begin, const int end) {
//                                            ^^^^^^^^

Same thing here:

void parseRepeat(const std::string repeatLine, int &begin, int &end) {
// Should probably be
void parseRepeat(const std::string& repeatLine, int &begin, int &end) {
//                               ^^^

Casting is nearly always a sign that something is wrong with your design:

(unsigned int)fromLine

This should be a hint that fromLine is the wrong type. Since it is measuring a size and will never by less than 0 this is an indication that the correct type for the type is unsigned int (or probably size_t).

void parseLines(const std::vector<std::string> text, std::size_t const begin, std::size_t const end) {
    Stack<int> lyricStack;

    std::size_t fromLine = begin;
    std::size_t toLine   = end;

    while(fromLine <= toLine && fromLine < text.size()) {

atoi() is fast but non standard and not always available. An easier way is to just use the stream operators. This will always work and 99% of the time will be sufficiently fast. Only optimize out when you know it makes a difference.

Also this code is so dense it is nearly unreadable. White space is your friend.

void parseRepeat(const std::string repeatLine, int &begin, int &end)
{
    std::string numbers = repeatLine.substr(repeatLine.find(" ") + 1);
    begin = atoi((numbers.substr(0, numbers.find(" "))).c_str()) - 1;
    end = atoi((numbers.substr(numbers.find(" "))).c_str()) - 1;
}

Much easier to write with streams:

void parseRepeat(const std::string repeatLine, int &begin, int &end)
{
    // This line always has the form 
    // #repeat <number> <number>
    std::stringstream   linestream(repeatLine);
    std::string         repeat;

    linestream >> repeat >> begin >> end;
}

Both NODE and Stack contain RAW pointers. Yet they do not obey the rule of three. This is very dangerous. The simple rule is your classes should never contain RAW pointers (all pointers should be wrapped in smart pointers) unless you are writing a smart pointer or container.

In this situation NODE would be easy to implement using smart pointer.

Also you do a work handling node inside stack. It simplifies the design if you move this work to the constructor of NODE. This makes the code in Stack much easier to read as it just handles the stack and the NODE can handle itself.

The Stack is arguably a container so it can have a pointer but you must implement the rule of three. This means you need to implement the Copy Constructor/Assignment operator/Destructor or make these methods private. The reason is that if you do not then the compiler will automatically generate these methods. And the compiler generated version does not plat well with "OWNED RAW pointers".

{
    Stack<int>   a;
    a.push(4);

    Stack<int>   b(a);   // Copy made of a

    DO STUFF
} // Here B is destroyed. 
  // But because you did not define a copy constructor b is a shallow copy of a
  // This means they both contain the same pointer. So b deletes it first.
  // Now A is destroyed.
  // This also deletes its pointer (the same as b) but it has already been deleted. 
  // Your program is now free to produce nasal daemons (undefined behavior).

The simplest solution is to disable copy construction and the assignment operator.

You have over complicated push:

if(!head) {
    newNode->next = NULL;
    head = newNode;
} else {
    newNode->next = head;
    head = newNode;
}

Would this not be easier to write as:

newNode->next = head;
head          = newNode;

Also isEmpty() is over complicated:

if(!head) {
    return true;
}

return false;

Could be written as:

return head == NULL;
\$\endgroup\$
  • \$\begingroup\$ What a great reply \$\endgroup\$ – John Dibling Nov 23 '11 at 20:43
  • \$\begingroup\$ Is there any compelling reason not to use a smart pointer for my Stack class? \$\endgroup\$ – cactusbin Nov 24 '11 at 3:38
  • \$\begingroup\$ Personally I would (just use a smart pointer). \$\endgroup\$ – Martin York Nov 24 '11 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.