Dequeue iterator not dereferencable

Question

Through doing a little research online, I've found that this is error is caused by trying to pop something off an empty stack. In my code, I thought I tried to make sure this exact thing wouldn't happen by storing the top of my stack in a temporary string called c, but for some reason the error keeps occurring. This is a project related to converting infix notation to postfix notation. When I input 1+2+3, I should get 12+3+, but instead this error occurs. The error occurs in the precedence while loop.

stack <string> InfixToPostfix(char * expr)
{
  // YOUR CODE STARTS HERE! 
 char* token;
 stack<string> s;
 string postfix;
 stack<string> p;
                                     // use stack s to manipulate the infix      to postfix
 s.push("(");
  token = strtok (expr," "); // get the first token
  while(!s.empty())
  {
          if(token=="(")
        {
            s.push(token);
          }
         else if(token==")")
      {
            string c=s.top();
            s.pop();
             while(c != "(")
            {
            postfix += c + " ";
            c = s.top();
            s.pop();
        }
  }
  else if(isNumber(token))
  {
      postfix+=token;
  }
  else 
  {
      while(precedence(s.top())>=precedence(token))
      {
          //put on bottom if need be

           string c = s.top();
            s.pop();
            postfix += c;
            postfix += " ";
      }
      s.push(token);
  }

token = strtok(NULL, " "); // use blanks as delimiter
  if (token == NULL) // no more tokens, exit the loop
     break;
  }
  p.push(postfix);
  return p;
}

Why dont you just use .empty() method to check if your stack is empty ? — KostasRim, Nov 11 '15 at 20:20
How so? Wouldn't the condition I put in my outer while loop cover that? — Gary, Nov 11 '15 at 20:22
you should always check if your stack is empty before poping an element. You dont do that in your if statements — KostasRim, Nov 11 '15 at 20:27
My entire while loop only functions if the stack isn't empty though. Adding that condition in an if statement hasn't helped as of yet. I do very much appreciate your response though. Any help I can get is good help because this error is frustrating — Gary, Nov 11 '15 at 20:33
@Gary `if(token=="(")` This is not how you compare C-style strings. Your entire code is flawed due to this issue. Use `strcmp`. — PaulMcKenzie, Nov 11 '15 at 20:41
@Paul, thank you. I don't know much about C-style strings, but making these changes helped my code run. Along with one more unrelated change. — Gary, Nov 12 '15 at 04:59

score 0 · Answer 1 · edited May 23 '17 at 11:51

Inside the if statements within the main while loop, you have some calls to pop() without checking if the deque is empty for example

 while(c != "(") {
     postfix += c + " ";
     c = s.top();
     s.pop();
 }

This should probably be:

while(c != "(" && !s.empty()) {

}

And the same below

while(precedence(s.top())>=precedence(token))
{
      //put on bottom if need be
      string c = s.top();
      s.pop();
      postfix += c;
      postfix += " ";
 }
 s.push(token);

These are quite likely sources of invalid access. In general you should try to use gdb or valgrind --tool=memcheck which will show you the source of error. Or any other debugger really...

Also if the token is a single character as I suspect it should be, make it a char not a char *. Then in your token comparisons use token == ')' (note the single quotes) which compares two characters and not what you have now which compares a char pointer with a string literal... This will probably apply to all the data structures that you maintain as well which should become, e.g. deque<char> ...

Finally pick up any decent introductory C++ book and read it. You will thank yourself later.

Dequeue iterator not dereferencable

1 Answers1