4
\$\begingroup\$

I have recently been trying to build a parser. After a month of trying and getting nowhere fast I decided, like I should have at begining, to research how parsers work and what they do.

After a little research, I learned that parsers create a tree like structure of the language grammar, official called a abstract syntax tree. After researching more, I then learned that I could create a AST using stacks.

I figured I could create a stack using a linked list in C++. Yes I know that their some standard library containers that could probably(more efficiently as well) do the same thing. I decided however, that since I'm still learning C++, I should make my own. It didn't seem to hard, and looked like a fun project.


To get the basics of what I needed to do, I followed this tutorial series. After getting the basic framework from the tutorial, I added several more functions to my linked list class that do some basic operations. I'll try to give a brief overview of the functions, although there pretty self-explanatory.

  • add_node(). Adds an element.
  • delete_node(). Removes an element.
  • print_stack(). Prints the entire stack.
  • pop(). Deletes the first element from the stack.
  • push(). Deletes the last element from the stack.
  • size(). Gets the size(as in the number of elements) of the stack.
  • last(). Gets the last element in the stack.
  • at(). Gets the element at the given index.
  • get_next(). Gets the element at the index after the index the given index.

And here's what everyone really wants; the code dump:

stack.h

#ifndef STACK_H
#define STACK_H

#include <iostream>
using std::cout;
using std::endl;
#include<string>

template <typename T>
class Stack {
private:
    typedef struct node {
        T data;
        node *next;
    } *node_ptr;

    node_ptr head;
    node_ptr curr;
    node_ptr temp;

public:
    Stack();
    void add_node(T add_data);
    void delete_node(T del_data);
    void pop();
    void push();
    void print_stack();

    int size();
    T last();
    T at(int index);
    T get_next(int index);
};
#endif

stack.cpp

#include "stack.h"

template <typename T>
Stack<T>::Stack() {
    head = NULL;
    curr = NULL;
    temp = NULL;
}

template <typename T>
void Stack<T>::add_node(T add_data) {
    node_ptr n = new node;
    n->next = NULL;
    n->data = add_data;

    if (head != NULL) {
        curr = head;
        while (curr->next != NULL) {
            curr = curr->next;
        }
        curr->next = n;
    } 
    else {
        head = n;
    }
}

template <typename T>
void Stack<T>::delete_node(T del_data) {
    node_ptr del_ptr = NULL;
    temp = head;
    curr = head;
    while (curr != NULL && curr->data != del_data) {
        temp = curr;
        curr = curr->next;
    }
    if (curr == NULL) {
        cout << "Error: [" << del_data << "] was not in the stack" << endl; 
        delete del_ptr;
    } 
    else {
        del_ptr = curr;
        curr = curr->next;
        temp->next = curr;
        if (del_ptr == head) {
            head = head->next;
            temp = NULL;
        }
        delete del_ptr;
        cout << "The value [" << del_data << "] was deleted" << endl;
    }
}

template <typename T>
void Stack<T>::pop() {
    temp = head;
    head = head->next;
    delete temp;
}

template <typename T>
void Stack<T>::push() {
    if (head->next == NULL) {
        delete head;
        head = NULL;
    }
    else {
        node_ptr next_to_end = head;
        node_ptr end = head->next;
        while (end->next != NULL) {
            next_to_end = end;
            end = end->next;
        }
        delete end;
        next_to_end->next = NULL;
    }
}


template <typename T>
void Stack<T>::print_stack() {
    curr = head;
    while (curr != NULL) {
        cout << curr->data << endl;
        curr = curr->next;
    }

}

template <typename T>
int Stack<T>::size() {
    node_ptr p = head;
    int count;
    while (p != NULL) {
        count++;
        // this is used to increment p to the next node
        // in the linked list. Once be equals NULL
        // the while loop will break
        p = p->next;
    }
    return count;
}

template <typename T>
T Stack<T>::last() {
    if (head == NULL) {
        return head->data;   
    }
    else {
        node_ptr end = head;
        while (end->next != NULL) {
            end = end->next;
        }
        return end->data;
    }
}

template <typename T>
T Stack<T>::at(int index) {
    curr = head;
    int count = 0;
    while (curr != NULL){
        if (count == index){
            return curr->data;
        }
        count++;
        curr = curr->next;
    }
    if (curr == NULL) {
        cout << "Error: [" << index << "] does not exist" << endl; 
    }

}

template <typename T>
T Stack<T>::get_next(int index) {
    curr = head;
    int count = 0;
    while (curr != NULL){
        if (count == index){
            return curr->next->data;
        }
        count++;
        curr = curr->next;
    }
    if (curr == NULL) {
        cout << "Error: [" << index << "] does not exist" << endl; 
    }
}

template class Stack<int>;
template class Stack<float>;
template class Stack<char>;
template class Stack<std::string>;
\$\endgroup\$
  • \$\begingroup\$ Question: why not use std data structures? There's std::stack already there. \$\endgroup\$ – MatthewRock Sep 14 '16 at 9:42
  • \$\begingroup\$ @MatthewRock I explained my reasons on the third paragraph from the top. And also, this was more of a test. This wasn't supposed to be an accurate stack, but rather a test for a project I'm working on. \$\endgroup\$ – Christian Dean Sep 14 '16 at 16:20
8
\$\begingroup\$

Remove functions that don't correspond to the "stack" abstration

The member functions you need that correspond to "stack" are:

  void push(T const& d);

  void pop();

  T const& top() const;

  size_t size() const;

  bool empty() const;

The other member functions that you need are:

  1. Default constructor
  2. Copy constructor
  3. Destructor
  4. Copy assignment operator

See The Rule of Three to understand why you need these functions. When you understand move semantics, you can add:

  1. Move constructor.
  2. Move assignment operator.

Here's the complete list of member functions you should have:

  Stack();

  Stack(Stack const& copy);

  ~Stack();

  void push(T const& d);

  void pop();

  T const& top() const;

  size_t size() const;

  bool empty() const;

  Stack& operator=(Stack const& rhs);

Remove unnecessary member data

The only member variable you need to implement a "stack" is

  node_ptr top_;

You can support all the member functions with just that. If size() is called often, it is worthwhile to add a member variable that keeps track of the size of the stack for the sake of efficiency.

  size_t size_;

Don't use std::cout or std::cerr for exception handling

Use std::exception for exception handling instead of writing textual output to std::cout or std::cerr.

Prefer nullptr to NULL

If you are able to use a compiler that supports C++11 or higher, prefer to use nullptr instead of NULL.

Implement templates in .h files

You cannot implement class templates or function templates in .cpp files. See Why can templates only be implemented in the header file?.

Put public section first and private section last

Users of your class shouldn't care about the private section of your class. The should only care about the public section of your class. For that reason, I recommend putting the public section of the class first and private section of the class last.


My suggestion for the class:

template <typename T>
class Stack {

   public:

      Stack();

      Stack(Stack const& copy);

      ~Stack();

      void push(T const& d);

      void pop();

      T const& top() const;

      size_t size() const;

      bool empty() const;

      Stack& operator=(Stack const& rhs);

   private:
      typedef struct node {
         T data_;
         node *next_;
      } *node_ptr;

      node_ptr top_;
      size_t size_;
};
\$\endgroup\$
  • \$\begingroup\$ I would also like to add that exceptions doesn't cost anything when they are not thrown, but if throw happens, it will have considerable impact on performance. \$\endgroup\$ – Incomputable Sep 13 '16 at 8:51
  • \$\begingroup\$ I really didn't add cout and endl as error checkers, but yet a way to debug. The example I posted was just a test. I am making a better linked list class the will include iterators, and proper error checking. \$\endgroup\$ – Christian Dean Sep 14 '16 at 1:40
3
\$\begingroup\$

Why is temp a field? the only times it is used it may as well be a local variable.


Besides that if you are using it for parsing then you will be popping and pushing nodes often. So it may be worth reducing allocation cost on that by keeping a linked list of previously allocated nodes:

node_ptr freelist; //init to null

void push(T const& d){
    node_ptr new_node;
    if(freelist){
        new_node = freelist;
        freelist = freelist->next;
    }else{
        new_node = new node;
    }
    new_node->data = d;
    new_node->next = head;
    head = new_node;
}

T&& pop(){
    node_ptr t = head;
    head = head->next;
    t->next = freelist;
    freelist = t;
    return std::move(t->data);
}

and in the destructor you will need to destroy them all like you need with the nodes actually on the stack:

while(freelist){
    node_ptr t = freelist;
    freelist = freelist->next;
    delete t;
}
\$\endgroup\$
3
\$\begingroup\$
#ifndef STACK_H
#define STACK_H

Prefer to give macros unique names. Macros do not obey scope rules and if a common name collides with a symbol of the same name, problems will occur. You can add uniqueness to the name by employing a naming convention.

Let's say the file could be found in \mylib\container\stack.hpp. I could use a common directory structure header layout with a randomly generated universal unique identifier:

#ifndef MYLIB_CONTAINER_STACK_HPP_QI7Z5IROSCOI48CJ0UHC
#define MYLIB_CONTAINER_STACK_HPP_QI7Z5IROSCOI48CJ0UHC

The symbol is still vulnerable to collisions, but the likelihood of someone declaring a macro name of the same format won't be nearly as often. This example uses random.org's random string generator.


// stack.h
#include <iostream>
#include <string>

Only #include what you need for the local translation unit to compile. Neither are required by the header (but are required in the implementation).

Many common implementations of <iostream> inject a static constructor into every translation unit that includes it. Be aware of this and avoid #include <iostream> unless it's absolutely necessary. Prefer <iosfwd> and use references to std::istream/std::ostream objects.


using std::cout;
using std::endl;

Do not use using directives or declarations at the global scope of header files. Doing so pollutes the global namespace of anyone using that header which may lead to symbol collisions and ADL misbehavior.


    typedef struct node {
        T data;
        node *next;
    } *node_ptr;

C-struct aliasing rules only exist in C++ because of compatibility. Prefer to use C++ style aliasing unless you are writing specifically for C.

    struct node {
        T data;
        node* next;
    };

    using node_ptr = node*;

    void add_node(T add_data);
    void delete_node(T del_data);
    void pop();
    void push();
    void print_stack();

    T last();
    T at(int index);
    T get_next(int index);

It is important to get the interface correct so users are not surprised. Conceptually, a stack is a container that operates on one end of a sequential collection. The two important operations are push (adds an element to the collection) and pop (removes an element from the collection).

push does not add elements to the collection in your implementation. Surprise!

You shouldn't provide direct access to the full linked list as that is not the concern of Stack. Stack is only concerned about the last element.

Strive for const-correctness. Immutable types should be specified by const (read-only). C++11 allows immutable literal types to be specified by constexpr instead.

For methods that only inspect the internals of an object (immutable), specify const.

    void pop();
    void push(const T&); // const specified parameter (read-only)

    T& last();             // Mutable access on reference
    const T& last() const; // Immutable access on reference

C++11 introduced move semantics, so we have 2 more ways of adding elements to the collection. Tackle these as a next step.

    void push(T&&);  // C++11 Move support
    T& emplace(T&&); // C++11 Move support

std::size_t is guaranteed to represent the size in bytes of any object. This is very useful for representing indices of unknown limits.

    std::size_t size() const;
    bool empty() const;

template <typename T>
Stack<T>::Stack() {
    head = NULL;
    curr = NULL;
    temp = NULL;
}

Prefer to construct data members through the member initializer list.

Prefer the literal type nullptr instead of the macro NULL.

template <typename T>
Stack<T>::Stack() 
  : head{nullptr}
  , curr{nullptr}
  , temp{nullptr} {
}

Do you really curr and temp? Both can be locally defined in the functions as they need them.

template <typename T>
Stack<T>::Stack() : head{nullptr} {}

Since C++11, if your constructor only initializes members to constants, prefer in-class member initializers.

class Stack {
    // ...
    node_ptr head{nullptr};
public:
    // no need to explicitly define Stack(), use compiler generated one.

template <typename T>
void Stack<T>::add_node(T add_data) {

When programming with generics, it's important that you realize what possible value types you are allowing to be passed as arguments. In this case, T can be any data type. T could be cheap to pass (primitives like int). T could be expensive (std::vector<std:vector<int>>). We don't know what might be passed, so we have to assume the worse happens. When passing data whose copying cost is or might be expensive, prefer to pass arguments by reference.

As earlier, if the data stored is immutable, specify const.

template <typename T>
void Stack<T>::add_node(const T& add_data) {

    if (head != NULL) {

Literals types are implicitly convertible to bool, so you don't need to explicitly check. 0, NULL (which is just a macro for 0), or nullptr all implicitly convert to false, so if head is NULL, the conditional evaluates to false. If head is any other value, the conditional evaluates to true.

    if (head) {

int Stack<T>::size() {
    // ...
    int count;
    // ...
        count++;

Used-before-set error here. Always initialize variables.

T Stack<T>::last() {
    if (head == NULL) {
        return head->data;   
    }
    else {
        // ...
        return end->data;
    }
}

Dereferencing a null pointer is undefined behavior. Rather than trying to access the null pointer, notify the callee that they cannot access an empty stack by throwing an exception.

Avoid else after interrupts in flow control (return, continue, break, throw). The control path will not execute the remaining code in the parent scope.

T could be expensive to return-by-value, so return-by-reference. Return-by-reference allows direct access to the value, so make sure both the return type is immutable (const T&) and that the function is inspecting only (last() const).

const T& Stack::last() const { if (!head) { throw std::runtime_error("Stack<>::last(): empty stack!"); } // ... return end->data; }

If you want to allow mutability to the last element so users don't have to peek->pop->push to change the top element, then provide a separate function that supports mutability.

T& Stack<T>::last() {
    if (!head) {
        throw std::runtime_error("Stack<>::last(): empty stack!");
    }
    // ...
    return end->data;
}

T Stack<T>::at(int index) {
    // ...
    if (curr == NULL) {
        // ...
    }
}

Falling off the end of a non-void function is undefined behavior. This occurs with at and get_next.


Know and apply the Rule of Zero, Three, Five. When classes are concerned with ownership semantics, they should define all five special member functions:

  1. Destructor
  2. Copy Constructor
  3. Copy Assignment Operator
  4. Move Constructor
  5. Move Assignment Operator

Objects that do not deal with ownership don't need to worry about defining those operators and should use the compiler generated ones.

Your class currently deals with ownership as it allocates/deallocates memory on the heap. Stack currently uses the default destructor generated by the compiler. When the destructor is called, the pointer itself is destroyed but the object the pointer was pointing to was not. This is a resource leak. To fix it, you need to implement a destructor and delete all the pointed to objects. By defining the destructor, you need to define the remaining 4 special member functions.

For Stack, we could have applied the rule of zero here by simply having another container type deal with the ownership. Your title says exactly what to do.

Stack, using linked list, for parser

Have your Stack use the linked list, not be the linked list. Apply the adaptor pattern.

  • Stack::push - calls std::list::push_back
  • Stack::pop - calls std::list::pop_back
  • Stack::peek - calls std::list::back()

Internally, std::list deals with the data ownership/management, so the 5 special member functions are not required to be defined for Stack.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the great critique. In response to you asking: Do you really need to explicitly instantiate your template?, Yes I have to declare all of possible types that can be passed into the template since I'm not implementing the class definition in the header file only. \$\endgroup\$ – Christian Dean Sep 14 '16 at 3:52
  • \$\begingroup\$ Sorry, there was a point I was going to make but I apparently never completed that thought. Just going to remove it. \$\endgroup\$ – Snowhawk Sep 14 '16 at 4:41
1
\$\begingroup\$

nicely laid out code, goodish names, no using namespace std, ++

no comments --

the 'normal' operations for a stack are

Push(T)
T Pop()
T Peek()
bool IsEmpty()

I dont understand what push() would do without reading the code. The point is that its a surprise

Naming conventions

Have a naming convention for member variables

node_ptr head_;
node_ptr curr_;
node_ptr temp_;

or

node_ptr m_head;
node_ptr m_curr;
node_ptr m_temp;

Be consistent with your class names, Stack vs node, should be Node

strictly speaking add_node doesnt add a node, it adds an element. A 'node' is an implementation detail. And anyway I would have it, I would only have push.

Think about copy semantics. All you methods take and return T instead if T&. You are doing a lot of copying, fine for int or string but maybe not for pushing complex things.

error handling

what are your guratntees, what if add (push) fails? You either must return something to indicate failure, or you must throw. I am a throwing advocate, but you must choose. You can just write to cout. What if this is headless code? You should write to a log if you can but not naked cout (good loggin is one of the hardest things in a code project)

\$\endgroup\$
  • 3
    \$\begingroup\$ In C++ the top of the stack is usually accessed with T& top() not T Peek(). Also in C++ its more common to see function/method names start with a lower case letter. Additionally using a naming convention as you suggest suggests badly named members. I would suggest using good names rather than following arbitrary conventions. \$\endgroup\$ – Martin York Sep 13 '16 at 0:02

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.