Iterator not dereferencable stack (expression tree) & loop does not work properly

Question

I am trying to convert infix to postfix and prefix by using tree in c++. I pass the infix expression to the createTree function and in the code I use 2 stack node(to store the operand and operator that has been poped from the stack s) and stack s(to store the operator). The code works finely when I input expression that has same precedence operators or the first operator has higher precedence than the second one. ex: 1*2/3 or 1/2+3. But it will debug when I input expressions which the first operator has lower precedence than the second one. for example : 1+2/3. I try to debug it and found DEBUG_ERROR("iterator not dereferencable"); I try to find in the internet and all those problems related to vector which I have never used before. I hope you guys could help me

  node *CreateTree(string post)
{
node *temp, *op1 , *op2;
stack<node*> tree;
stack<char> s;
int i = 0;
while (!tree.empty())
{
    tree.pop();
}
for(i = 0; i<post.length();i++)
{
    if (post[i]==' ') continue;
    else if(IsOperand(post[i]))
    {
        node *temp = new node();
        temp->in = post[i];
        temp->left = NULL;
        temp->right = NULL;

        for(int j=i+1;j<post.length();j++)
        {
            if (IsOperand(post[j]))
            {
                temp->in+=post[j];
                i = j;
            }
            else break;
        }
        tree.push(temp);
    }
    else if(isOperator(post[i]))
    {
        while(!s.empty() && s.top()!='(' && s.top()!='{' && s.top()!='[' && !hasHigherPrecedence(post[i],s.top()))
       {
            node *op1;
            node *op2;
            op2 = tree.top();
            tree.pop();
            op1 = tree.top();
            tree.pop();
            node *temp = new node();
            temp->in = s.top();
            temp->left = op1;
            temp->right = op2;
            root = temp;
            s.pop();
            tree.push(root);
       }
        s.push(post[i]);
    }
    else if(post[i]=='(')
   {
       s.push(post[i]);
   }
   else if(post[i]==')')
   {
       while(s.top()!='('&&!s.empty())
       {
            node *op1;
            node *op2;
            op2 = tree.top();
            tree.pop();
            op1 = tree.top();
            tree.pop();
            node *temp = new node();
            temp->in = s.top();
            temp->left = op1;
            temp->right = op2;
            root = temp;
            s.pop();
            tree.push(root);
       }
       s.pop();
   }
   else if(post[i]=='[')
   {
       s.push(post[i]);
   }
   else if(post[i]==']')
   {
       while(s.top()!='['&&!s.empty())
       {
            node *op1;
            node *op2;
            op2 = tree.top();
            tree.pop();
            op1 = tree.top();
            tree.pop();
            node *temp = new node();
            temp->in = s.top();
            temp->left = op1;
            temp->right = op2;
            root = temp;
            s.pop();
            tree.push(root);
       }
       s.pop();
   }
   else if(post[i]=='{')
   {
       s.push(post[i]);
   }
   else if(post[i]=='}')
   {
       while(s.top()!='{'&&!s.empty())
       {
            node *op1;
            node *op2;
            op2 = tree.top();
            tree.pop();
            op1 = tree.top();
            tree.pop();
            node *temp = new node();
            temp->in = s.top();
            temp->left = op1;
            temp->right = op2;
            root = temp;
            s.pop();
            tree.push(root);
       }
       s.pop();
   }
   else cout<<post[i]<<" is not registered as operator or operand";
}
while (!s.empty())
{
    node *op1;
    node *op2;
    op2 = tree.top();
    tree.pop();
    op1 = tree.top();
    tree.pop();
    node *temp = new node();
    temp->in = s.top();
    temp->left = op1;
    temp->right = op2;
    root = temp;
    s.pop();
}
return root;
}

below is the functions that are called in code above

bool isOperator(char a)
{
      return(a=='+' || a=='*' || a=='^' || a=='/' ||
       a=='-' || a=='%')? true:false;
}

int getWeight(char op)
{
 int weight;
 switch(op)
{
    case '+' : case '-':
        weight = 1;
        break;
    case '*':
    case '/':
    case '%':
        weight = 2;
        break;
    case '^':
        weight = 3;
        break;

}
return weight;

}

bool hasHigherPrecedence(char a, char top)
{
   int aW = getWeight(a);
   int tW = getWeight(top);
   return (aW > tW)? true : false;
}

I don't see the bug in the code you posted, so I think it must be in code you didn't post. I assume you are using tree.top() when tree is empty. If other code were correct tree could not be empty at that point. But since it is not locally obvious that tree isn't empty, you should have at least an assert and maybe a run time check. — JSF
Notice it is locally obvious that s is not empty at the point where you use s.top(). But the same is not true of tree. Even if you were not debugging a current problem, it is good practice to have an assert where your code makes an assumption (tree.size()>=2) that is not locally obvious. — JSF
The memory leak each time (in the quoted code) you do something like node *op2 = new node(); is NOT related to the problem you are trying to diagnose, but should also be fixed. It is best to delay declaring the variable until you have its correct initial value node *op2 = tree.top();. Alternately it is OK to just declare it without an initial value node *op2; as long as a compiler can easily see that all paths from there that use it also initialize it. If neither of those fits, then initialize to 0 node *op2=0; rather than creating an object just to leak it. C++ is not Java — JSF
Hi thank you for your response. I tried your sugestion for memory leak and it works for op1 and op2 but not the temp. I will edit the code — NatJ

NatJ NatJ · Accepted Answer · 2015-11-18T07:06:05

I have found my answer i just forget to insert tree.push(root)

while (!s.empty())
{
    node *op1;
    node *op2;
    op2 = tree.top();
    tree.pop();
    op1 = tree.top();
    tree.pop();
    node *temp = new node();
    temp->in = s.top();
    temp->left = op1;
    temp->right = op2;
    root = temp;
    tree.push(root);//I forgot this
    s.pop();
}

Iterator not dereferencable stack (expression tree) & loop does not work properly

1 Answers