Segmentation fault

[andersonwq]

I am pretty sure that I am getting a segmentation fault because of the '(' in my function. The function is suppose to check the grouping of an equation.

template<class type>
void stack<type> :: search ()
{
        int tmp=0;
        int tmp2=0;
        int tmp3=0;
        int tmp4=0;

        node<type>* cur=head;
        while(cur != NULL)
        {
                cur=cur -> next;

        if(cur-> data == '(')
                tmp++;
          if(cur -> data == ')')
                tmp2++;


        if(cur-> data == '{')
                tmp3++;
          if(cur -> data == '}')
                tmp4++;

}
        if (tmp == tmp2)
                cout << "The operation has the correct amount of parenthesis." << endl;

        else
                cout << "You do not have the appropriate number of parenthesis." << endl;

        if (tmp3 == tmp4)
                cout << "The operation has the correct amount of braces." << endl;

        else
                cout << "You do not have the appropriate number of braces." << endl;


}

[firedraco]

I'm pretty sure line 12 is your problem. You don't ever check if cur->next is NULL.

[sorthon123]

right it does not check for NULL but its not NULL so it doesn't really matter at this point. i tried checking for that but it doesn't change anything

[sorthon123]

when debugging it says the segmentation fault is if(cur-> data == '(') there

[hanst99]

Um... think very closely about what you are doing here.

 while(cur != NULL)
        {
                cur=cur -> next;

I'll give you an example. What happens if cur exists, but cur-> next is NULL?

hint: in this case, a do..while loop is probably the best approach.

[sorthon123]

did the do while as well but still returns a segmentation fault, the fault isnt do to a jump after the last null pointer the problem is in the if statements with in the while loop

[hanst99]

You really don't listen now, do you?

The problem is, you check whether cur is NULL or not. Then you set cur to cur-> next. The problem is that cur->next can very well be null, but you don't check for that at all, and happily dereference cur as if it was ok.

if (cur!=NULL) do
{
        if(cur-> data == '(')
                tmp++;
          if(cur -> data == ')')
                tmp2++;


        if(cur-> data == '{')
                tmp3++;
          if(cur -> data == '}')
                tmp4++;
   cur=cur -> next;

} while (cur!=NULL);

[sorthon123]

sept it does check for it... if cur->next is NULL then it wont do the while loop so really a do while here wont work at all because if in fact it is null it will try and run the if statements anyway.

[sorthon123]

and even with your changes you still get a segmentation fault

[sorthon123]

so if your going to add the if(cur!=NULL) then why use a do while at all?

[sorthon123]

and like i said before that doesn't change the fact that when ran through a de bugger the issue lies in the if statements trying to compare whats in the list to '('

[hanst99]

The if is just to check if the head is NULL and is only executed once, for the rest I have just done a do..while cause I kinda like it better.

PS: Do you actually set your pointers to NULL when you create a new node? Because if not they could still contain trash data from before, and then your program explodes anyways even with you checking for NULL.

[sorthon123]

node<type>* cur=head;

so the node starts at head and if nothing is pushed into the list then head is NULL

[sorthon123]

here is the entire program

#include <iomanip>
#include <iostream>
#include <typeinfo>
#include <cstdlib>

using namespace std;

// Specification file for a linked list abstract data type class.
// This linked list is actually a stack, since all additions and
// removals are at the head.
template<class type>
struct node // Each node has two fields:
{
type data; // a data field,
node<type> *next; // and a pointer field.
};

template<class type>
class stack
{
private:
node<type> *head; // Pointer to the first cell.

public:
stack();
void push(type item);
bool pop();
void search();
void view();
bool empty();
bool full();

};

template<class type>
stack<type>::stack()
{
/* node<type>* temp=new node<type>;
temp-> data;
temp-> next=head;
*/
}

template<class type>
void stack<type> :: push (type item)
{

node<type> *t = new node<type>;
node<type> *tmp = new node<type>;
node<type> *trail = new node<type>;
trail = NULL;

if(head == NULL) //Startig the list
{
t-> data = item;
t -> next = head;
head = t;
}
else if(head != NULL)
{
t = head;
while(t != NULL){ //Puts inside the list
trail = t;
t = t->next;
}
tmp->data = item;
tmp->next = t;
trail->next = tmp;
}
}


// Function to remove the first element from the stack and
// return it to the caller.
template<class type>
bool stack<type> :: pop ()
{

node<type>* cur;
cur = head;
if(cur == NULL)
{
return false;
}

else
{
head = cur -> next;
delete cur;
return true;
}
}

// Accessor functions.
// Function to see whether an element is on the list.
template<class type>
void stack<type> :: search ()
{
int tmp=0;
int tmp2=0;
int tmp3=0;
int tmp4=0;

node<type>* cur=head;
while(cur != NULL)
{
cur=cur -> next;

if(cur-> data == '(')
tmp++;
if(cur -> data == ')')
tmp2++;


if(cur-> data == '{')
tmp3++;
if(cur -> data == '}')
tmp4++;

}
if (tmp == tmp2)
cout << "The operation has the correct amount of parenthesis." << endl;

else
cout << "You do not have the appropriate number of parenthesis." << endl;

if (tmp3 == tmp4)
cout << "The operation has the correct amount of braces." << endl;

else
cout << "You do not have the appropriate number of braces." << endl;


}

// Function to output the list for viewing. Assumes the
// data type is compatible with cout << .
template<class type>
void stack<type> :: view ()

{
node<type>* tmp = head;

while(tmp != NULL){
cout << tmp -> data;
tmp = tmp -> next;
}

}


// Is the list empty?
template<class type>
bool stack<type> :: empty ()
{
if(head == NULL)
return true;
else
return false;
}

// Is the list full?
template<class type>
bool stack<type> :: full ()
{
return false;
}




int main()
{


stack<char> b;

b.push('(');
b.push('8');
b.push('*');
b.push('9');
b.view();
b.search();
}

[hanst99]

template<class type>
void stack<type> :: push (type item)
{

node<type> *t = new node<type>;
node<type> *tmp = new node<type>;
node<type> *trail = new node<type>;
trail = NULL;

if(head == NULL) //Startig the list
{
t-> data = item;
t -> next = head;
head = t;
}
else if(head != NULL)
{
t = head;
while(t != NULL){ //Puts inside the list
trail = t;
t = t->next;
}
tmp->data = item;
tmp->next = t;
trail->next = tmp;
}
}

You cause memory leaks here. I'll leave the search to you. In this function, you should set the next member of newly created nodes to NULL instead of leaving it uninitialized. Oh and one question: Is there a specific reason you defined Stack and node as templates, considering they can only work with chars anyways?

[sorthon123]

ok but that doesn't help why our if statement if(cur->data == '(') gives a segmentation fault

[sorthon123]

they are set to templates because our professor used to always make us turn our old programs into templated ones so now we just do it out of habit.

[hanst99]

Actually, it does. If you don't initialize your pointers with NULL, they aren't guaranteed to be. Thus your pointers could point to memory regions your program has no access to, causing a segmentation fault. So we can't be sure whether cur really is a valid pointer in that situation.

they are set to templates because our professor used to always make us turn our old programs into templated ones so now we just do it out of habit.

Well yeah, but

cur->data == ')'

doesn't make any sense with datatypes other than char, so writing it as a template is not only pointless, but plain wrong. It's not really a template, you're just making it look like one.

[sorthon123]

tried and failed it still doesn't like that we are checking for '(' and so on

[hanst99]

Well, you gotta get the idea that the seg fault is caused by the check out of your head. Seg faults are caused by dereferencing invalid pointers.