Can't identify memory access error in code, keeps giving segmentation faults

Question

I have tried creating a program that uses simple stack functions like push to add the contents of the statement onto a stack from where I then print out each character and then reverse the statement. I have used the '.' and '->' member access variables to change the contents of the struct based stack. Upon compiling it prints out the original statement, but after that it gives a segmentation error, saying I am attempting to dereference an uninitialised pointer. Can someone guide me as to how I should solve this problem as it isn't stating the line I have made the problem either.

#include <stdio.h>
#define MAX 1000
#define FULL (MAX - 1)
#define EMPTY -1

typedef struct stack {char s[MAX]; int top;} stack;
int top = EMPTY;

int isFull()
{
  if(top == FULL)
    return 1;
  else
    return 0;
}


int isEmpty()
{
  if(top == EMPTY)
    return 1;
  else
    return 0;
}


void reset(stack *stk)
{
  stk -> top = EMPTY;
}


void push(char c, stack *stk)
{
  stk -> top++;
  (*stk).s[(*stk).top] = c;
}


char pop(stack *stk)
{
  return (*stk).s[(*stk).top--];
}


void print(stack *stk)
{
  int i;
  while(1)
  {
    if(isEmpty())
    {
      printf("Stack underflow\n");
      break;
    }
    for(i = 0; i <= top; i++)
    {
      printf("%c\n", (*stk).s[i]);
    }
    printf("\n");
    return;
  }
}


void reverse(stack *stk)
{
  int i;
  while(1)
  {
    if(isEmpty())
    {
      printf("Stack underflow\n");
      break;
    }
    for(i = top; i >= 0; i--)
    {
      printf("%c", (*stk).s[i]);
    }
    printf("\n");
    return;
  }
}

char peek(const stack *stk)
{
  while(1)
  {
    if(isEmpty())
    {
      printf("Stack underflow\n");
      break;
    }
    return (*stk).s[(*stk).top];
  }
}


int main()
{
  stack stack_of_char;
  char *str = "i am otto am i";
  int i;
  reset(&stack_of_char);
  printf("original is: %s\n", str);
  while(str[i] != '\0')
  {
    push(str[i++], &stack_of_char);
  }
  print(&stack_of_char);
  reverse(&stack_of_char);
  return 0;
}

Answer 1

There are several issues with your program. Let's begin with the global variable top. This is causing problems because on the one hand you have a stack struct responsible for maintaining a stack, and that has its own top. But then you have this global which you're not even using anywhere. It's almost like you added it to get around compiler errors that you didn't understand ;)

So let's ditch that, and fix your stack functions. I'm rearranging the parameters of the push function so that the stack is the first argument. This is a bit more conventional.

typedef struct stack {
    char s[MAX];
    int top;
} stack;

int isFull(stack *stk)
{
    return stk->top == FULL;
}

int isEmpty(stack *stk)
{
    return stk->top == EMPTY;
}

void reset(stack *stk)
{
    stk->top = EMPTY;
}

void push(stack *stk, char c)
{
    if (isFull(stk))
        return;
    stk->s[++stk->top] = c;
}

char pop(stack *stk)
{
    if (isEmpty(stk))
        return '\0';
    return stk->s[stk->top--];
}

For the pop function, I arbitrarily return a NUL character if the stack is empty, because something must be returned. But really, you should never call this function if the stack is empty.

Let's look at your display functions now. The first thing I notice is that these are really convoluted. There is no need for that complexity. Look here:

void print(stack *stk)
{
    for(int i = 0; i <= stk->top; i++)
    {
        printf("%c\n", stk->s[i]);
    }
    printf("\n");
}

void reverse(stack *stk)
{
    for(int i = stk->top; i >= 0; i--)
    {
        printf("%c", (*stk).s[i]);
    }
    printf("\n");
}

char peek(const stack *stk)
{
    if (isEmpty(stk))
    {
        printf("Stack empty!\n");
        return '\0';
    }
    return stk->s[stk->top];
}

And so all that remains is a little tidy-up of your main function, and adjust the parameter order for push.

int main()
{
    const char *str = "i am otto am i";
    printf("original is: %s\n", str);

    stack stack_of_char;
    reset(&stack_of_char);
    for (int i = 0; str[i]; i++)
    {
        push(&stack_of_char, str[i]);
    }

    print(&stack_of_char);
    reverse(&stack_of_char);
}

Note also that you shouldn't really be walking over your stack with those functions. The typical way you would use a stack to reverse something is to push values onto it and then pop them off. So, you can print the string in reverse like this:

    // Pop characters from stack to print in reverse
    while (!isEmpty(&stack_of_char))
    {
        char c = pop(&stack_of_char);
        putc(c, stdout);
    }
    putc('\n', stdout);

Answer 2

Without initialization, the integer will be a random value. It is the root cause of the memory access error.

You will need to initialize the variable properly. In main function, instead of

int i;,

you should use

int i = 0;.

Assume that you plan to access the value starting from index 0.