Error: deque iterator not dereferenceable

Question

I'm trying to create a program that converts an arithmetic expression from infix to postfix form. As long as I don't call the "infixToPostFix" function, the program runs fine. But when I try to run the following code, I get a crash and error "deque iterator not dereferenceable". I can't find any dereferencing operators, so I'm not sure what's wrong:

// infixToPostfixTest.cpp

#include "Token.h"
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// infix to postfix function prototype

void infixToPostfix(vector<Token> &infix, vector<Token> &postfix);

// priority function prototype
int priority(Token & t);

// printing a Token vector
void printTokenVector(vector<Token> & tvec);

int main() {

  // Experiment
  //--------------------------------------------------
  vector<Token> infix;

  // a + b * c - d / e % f
  //
  infix.push_back(Token(VALUE,5.0));   // a
  infix.push_back(Token(OPERATOR,'+'));
  infix.push_back(Token(VALUE,6.0));   // b
  infix.push_back(Token(OPERATOR,'*'));
  infix.push_back(Token(VALUE,7.0));   // c

  cout << "Infix expression: ";
  printTokenVector(infix);


  vector<Token> postfix;  // create empty postfix vector
  infixToPostfix(infix, postfix);  // call inToPost to fill up postfix vector from infix vector

  cout << "Postfix expression: ";
  printTokenVector(postfix);
  cout << endl << endl;

  return 0;
}

// printing a Token vector
void printTokenVector(vector<Token> & tvec)
{
    int size = tvec.size();
    for (int i = 0; i < size; i++) {
        cout << tvec[i] << " ";
    }
    cout << endl;
}




int priority(Token & t) // assumes t.ttype is OPERATOR, OPEN, CLOSE, or END
{
    char c = t.getChar();
    char tt = t.getType();

    if (c == '*'    ||    c == '/')
        return 2;
    else if (c == '+'    ||    c == '-')
        return 1;
    else if (tt == OPEN)
        return 0;
    else if (tt == END)
        return -1;
    else
        return -2;
}

void infixToPostfix(vector<Token> &infix, vector<Token> &postfix)
{
    stack<Token> stack;

    postfix.push_back(END);

    int looper = 0;
    int size = infix.size();
    while(looper < size) {
        Token token = infix[looper];

        if (token.getType() == OPEN)
        {
            stack.push(token); 
        }

        else if (token.getType() == CLOSE)
        {
            token = stack.top();
            stack.pop();

            while (token.getType() != OPEN)
            {
                postfix.push_back(token);

                token = stack.top();
                stack.pop();

            }
        }

        else if (token.getType() == OPERATOR)
        {
            Token topToken = stack.top();

            while ((!stack.empty()) && (priority(token) <= priority(topToken)))
            {
                Token tokenOut = stack.top();
                stack.pop();

                postfix.push_back(tokenOut);
                topToken = stack.top();
            }

            stack.push(token);
        }

        else if (token.getType() == VALUE)
        {
            postfix.push_back(token);
        }

        else
        {
            cout << "Error! Invalid token type.";
        }

        looper = looper + 1;
    }

    while (!stack.empty())
    {
        Token token = stack.top();
        stack.pop();

        postfix.push_back(token);
    }
}


//Token.h

#ifndef TOKEN_H
#define TOKEN_H

#include <iostream>
using namespace std;

enum TokenType { OPEN, CLOSE, OPERATOR, VARIABLE, VALUE, END };

class Token {

public:
    Token (TokenType t, char c) : ttype(t), ch(c) { }
    Token (TokenType t, double d) : ttype(t), number(d) { }
    Token (TokenType t) : ttype(t) { }
    Token () : ttype (END), ch('?'), number(-99999999) { }

    TokenType getType() {return ttype;}
    char getChar() {return ch;}
    double getNumber() {return number;}

private:
    TokenType ttype;
    char ch;
    double number;
};

ostream & operator << (ostream & os, Token & t) {

    switch (t.getType()) {
        case OPEN:
            os << "("; break;
        case CLOSE:
            os << ")"; break;
        case OPERATOR:
            os << t.getChar(); break;
        case VARIABLE:
            os << t.getChar(); break;
        case VALUE:
            os << t.getNumber(); break;
        case END:
            os << "END" ; break;
        default: os << "UNKNOWN";
    }


    return os;
}       

Answer 1

I ran into this problem too. I think the problem is in this sort of code:

    else if (token.getType() == CLOSE)
    {
        token = stack.top();
        stack.pop();

        while (token.getType() != OPEN)
        {
            postfix.push_back(token);

            token = stack.top();
            stack.pop();

        }
    }

The problem is that 'token' is a reference to the top, not a copy. So you can't pop the stack until you are done working with token. In my case, it often still worked because the information was still present, but then it would crash at weird times. You need to organize this code in a different way to pop only after you done working with 'token'.

Maybe something like:

else if (token.getType() == CLOSE)
{
    token = stack.top();
    Token saveToken = new Token(token);  // Or something like this...
    stack.pop();

    while (saveToken.getType() != OPEN)
    {
        postfix.push_back(saveToken);

        token = stack.top();
        delete saveToken;     // ugh
        Token saveToken = new Token(token);
        stack.pop();

    }
    delete saveToken;  //ugh
}

Answer 2

You are calling top on empty stack, just follow the code for your test.

1. you start with an empty stack
2. you encounter a VALUE, you don't change stack
3. you encounter an OPERATOR and attempt to access stack.top()

Answer 3

stack is implemented using container, since stack is container adaptor, by default deque is used. In probably one line of your code - you call pop/top on empty stack, that is not allowed.

trace show, that error is after Token +. Problem is here:

   else if (token.getType() == OPERATOR)
    {
        Token topToken = stack.top();

You try to top from empty stack, since stack in case, where is only NUMBER token before OPERATOR token, is empty.