Stack of Tokens will not "pop()"

[tjp1588]

Hi, I am currently writing a program that converts an infix notation expression to postfix notation. Part of the program involves using a linked list to temporarily store Token objects (of type char or double). The code I am using seems to properly push() the tokens onto the stack. I am also able to return the top token from the stack using top(). However, whenever I make a call to pop() to remove the head node from the stack, my program craps out. I have been at this for weeks now trying to find solutions online and I am getting tired. I finally worked up the courage to post a request for help here since I often find myself frequently visiting this website.

The code here is definitely condensed. It does not contain my Expression class (which takes in an equation and converts it to postfix notation) and few other functions. However, regardless the program still does not work when trying to manipulate the stack using pop().

Thanks for any help, it is greatly appreciated.

#include <iostream>
#include <string>
#include <queue>
#include <string>
#include <cstdlib>
#include <cmath>

using namespace std;

/********************************************************************************/

/*************************************************
*
*
* This is the start of Token.h
*
*
*/
#ifndef TOKEN_H
#define TOKEN_H

enum TokenType {opType, valType};

class Token
{
    friend std::ostream& operator<<(std::ostream& o, Token t);
    public:
        Token(char c);
        Token(double d);
        bool isOp() {return type == opType;}
        bool isVal() {return type == valType;}
        char getOp() {return op;}
        double getVal() {return val;}
        int precedence();
    protected:
    private:
        TokenType type;
        char op;    /// if type == op, this field is valid
        double val; /// if type == number, this field is valid
};

#endif // TOKEN_H

/*
*
* This is the End of Token.h
*
*
*******************************************************/

/*****************************************************
*
*
*This is the start of Token.cpp
*
*
*/

Token::Token(char c)
{
    op = c;           // store the operator
    type = opType;    // set the type to be an operator
}

Token::Token(double d)
{
    val = d;          // store the value
    type = valType;   // set the type to be a value
}

// overloaded output operator
std::ostream& operator<<(std::ostream& o, Token t)
{
    if (t.isOp())
    {
        std::cout << "Operator: " << t.getOp();
    }
    else if (t.isVal())
    {
        std::cout << "Number:   " << t.getVal();
    }
}

int Token::precedence()
{
    switch (op)
    {
        case '!': return 8;
        case '^': return 7;
        case '*':
        case '/': return 6;
        case '+':
        case '-': return 5;
        //case gt,ge,lt,le: return 4;
        //case eq, ne : return 3;
        //case '&' : return 2;
        //case '|' : return 1;
        case '(': return 0;
  }
}


/*
*
*
* This is the end of Token.cpp
*
***********************************************************/



/**************************************************************************/

/****************************************************************************/

/*
*
*
* This is the beginning of LinkedList.h
*
*
*/
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

struct Node
{
    Node *next;
    Token *data;
};

class LinkedList
{
    friend ostream& operator<<(ostream &o, LinkedList ll);
    public:
        LinkedList();
        virtual ~LinkedList();
        void head_insert(Token s);
        int count();
        Token head_delete();
        bool empty() {return !head;}

    protected:
        Node *head;
        Node *tail;
    private:
        int count(Node *);

};

#endif // LINKEDLIST_H

/*
*
*
* This is the end of LinkedList.h
*
*
***************************************************************/

/****************************************************************************/
/*
*
*
* This is the beginning of LinkedList.cpp
*
*
*/

LinkedList::LinkedList()
{
    head = tail = NULL;
}

LinkedList::~LinkedList()
{
    //dtor
}

void LinkedList::head_insert(Token s)
{
    Node * n = new Node;



    if (!head)  // empty list
    {
        head = tail = n;
        head->data = &s;
        head->next = NULL;
    }
    else        // non-empty list
    {
        n->next = head;
        head = n;
        n->data = &s;
    }
}

ostream& operator<<(ostream &o, LinkedList ll)
{
    Node *ptr = ll.head;
    while (ptr != NULL)
    {
        o << ptr->data << ", ";
        ptr = ptr->next;
    }
    return o;
}

int LinkedList::count()
{
    return count(head);
}

int LinkedList::count(Node *list)
{
    if (!list)    {
        return 0;
    }
    else
    {
        return 1+count(list->next);
    }
}

Token LinkedList::head_delete()
{
    Token * retToken;

    if (!head)
    {
        cerr << "Attempting to delete from an empty list" << endl;
        exit(1);
    }

    if (head == tail)  // one element
    {
        retToken = head->data;
        delete head;
        head = tail = NULL;
        return *retToken;
    }

    retToken = head->data;
    Node *deleteMe = head;
    head = head->next;
    delete deleteMe;
    return *retToken;
}


/*
*
*
* This is the end of LinkedList.cpp
*
*
*******************************************************************/

/*****************************************************************************/

/************************************************************
*
*
* This is the beginning of Stack.h
*
*
*/
#ifndef STACK_H
#define STACK_H


class Stack : private LinkedList
{
  public:
      Stack();
      void push(Token element) {head_insert(element);}
      Token pop() {return head_delete();}
      Token top() {return *(head->data);}
      bool empty() {return head == NULL;}
  protected:
  private:
};

#endif //STACK_H

/*
*
*
* This is the end of stack.h
*
*
***************************************************************/

/****************************************************************************/

/**************************************************************
*
*
* This is the beginning of stack.cpp
*
*
*/


Stack::Stack()
{
    //ctor
}

/*
*
*
* This is the end of stack.cpp
*
*
***************************************************************/

/************************************************************************/

/**************************************************************
*
*
* This is the beginning of main.cpp
*
*
*/

int main()
{
    Stack s;

    // creating 4 tokens, 2 char, 2 doubles
    Token token1('+');
    Token token2('-');
    Token token3(90.21);
    Token token4(13.78);

    // pushing tokens onto the stack
    s.push(token1);
    s.push(token2);
    s.push(token3);
    s.push(token4);

    // attempting to pop (deletes head node) and display top (should be 90.21)
    s.pop();
    std::cout << s.top() << std::endl;


    return 0;
}

[kbw]

In function void LinkedList::head_insert(Token s) why do this?

    else        // non-empty list
    {
        n->next = head;
        head = n;
        n->data = &s;
    }

Are new nodes appended to the end or inserted at the head of the linked list?

Your linked list has member tail, but it's not set in that insert function.

Finally, why does the node hold a pointer to a Token rather than the Token itself?

[tjp1588]

New nodes are appended to the head of the linked list. There is a tail node because originally there was a tail insert function that would append them to the end of the list. However, I quickly realized that my function tail_insert() was not needed so I removed it. I did not however remove the node tail (must of slipped my mind).

I have tried to have the node hold the token itself (instead of a pointer) but it ended up creating more problems. At:

struct Node
{
    Node *next;
    Token *data;
};

When declaring a Token I have to initialize it as a char or a double, such as:

Token data('*');

Otherwise I cannot just simply declare it as:

Token data;

That is why I used a pointer.

[kbw]

The default copy of Token will do the right thing. (And even if it didn't you would make it so.) So the Node can hold a Token, and not just a pointer to a Token.

head_delete() uses tail, but it's not maintained in head_insert(), so there is some inconsistency there.

The link list is fine, my mistake.

The problem is pop works, but you call top after you've popped the stack. That's why you loose the value.

[tjp1588]

Yes, you were correct. I added a default Token constructor and removed the pointer for data and it worked (after a few other minor changes). Thanks a bunch for the help, I will mark as solved.