C stack implementation throws bad access error

Question

Am building a stack in C. Stack occasionally fails with a EXC_BAD_ACCESS error on the if check in my isEmpty() function, and I'm not sure why.

Typedefs & definitions:

#define NodeSize sizeof(StackNode)

struct stackNode {
    int data;
    struct stackNode *nextPtr;
};

typedef struct stackNode StackNode;
typedef StackNode *StackNodePtr;

Stack operation functions

void push(StackNodePtr *topPtr, int value) {
    
    // Declare a new node and set it to the top
    StackNode *node;
    node = malloc(sizeof(NodeSize));
    
    node->data = value;
    node->nextPtr = *topPtr;
    
    // Reassign the pointer to the top
    *topPtr = node;
    
    printStack(*topPtr);
}

int pop(StackNodePtr *topPtr) {
    
    StackNode *node = *topPtr;
    
    if (isEmpty(node)) {
        return 0;
    }
    
    // Grab the current top node and reset the one beneath it to the top pointer.
    *topPtr = node->nextPtr;
    
    printStack(*topPtr);
    
    return node->data;
}

int isEmpty(StackNodePtr topPtr) {
    if (topPtr == NULL || topPtr->nextPtr == NULL) { // BAD_ACCESS
        return 1;
    }
    return 0;
}

void printStack(StackNodePtr topPtr) {
    
    StackNode *iter = topPtr;
    
    // If the stack is immediately empty, just print that.
    if (!isEmpty(iter->nextPtr)) {
        
        // Iterate over each element in the stack and print its data
        for (;isEmpty(iter); iter = iter->nextPtr) {
            printf("%d ", iter->data);
        }
        printf("NULL");
    } else {
        printf("NULL");
    }
    
    printf("\n");
}

void evaluatePostfixExpression(char *expr) {
    
    // Create the stack and insert an initial parenthesis
    StackNode *head;
    head = malloc(NodeSize);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char token = expr[i];
        
        // If the current character is a digit
        if (token >= '0' && token <= '9') {
            push(&head, token - '0');
            
        // If it's an operator
        } else if (token == '+' || token == '-' || token == '*' || token == '/' || token == '^' || token == '%') {
            
            int x = pop(&head);
            int y = pop(&head);
            
            int result = calculate(y, x, token);
            push(&head, result);
        }
    }
    
    int output = pop(&head);
    
    printf("The value of the expression is: %d\n", output);
}

int calculate(int op1, int op2, char operator) {
    switch (operator) {
        case '+':
            return op1 + op2;
        case '-':
            return op1 - op2;
        case '*':
            return op1 * op2;
        case '/':
            return op1 / op2;
        case '%':
            return op1 % op2;
    }
    
    if (operator == '^') {
        int result = 1;
        for (int i = 0; i < op2; i++) {
            result *= op1;
        }
        return result;
    }
    return 0;
}

Even just a hint in the right direction would be appreciated.

Request for context:

int main() {
    char postfix[255] = "54*81+4/+";
    
    evaluatePostfixExpression(postfix);
    
    return 0;
}

void evaluatePostfixExpression(char *expr) {
    
    // Create the stack and insert an initial parenthesis
    StackNode *head;
    head = malloc(NodeSize);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char token = expr[i];
        
        // If the current character is a digit
        if (token >= '0' && token <= '9') {
            push(&head, token - '0');
            
        // If it's an operator
        } else if (token == '+' || token == '-' || token == '*' || token == '/' || token == '^' || token == '%') {
            
            int x = pop(&head);
            int y = pop(&head);
            
            int result = calculate(y, x, token);
            push(&head, result);
        }
    }
    
    int output = pop(&head);
    
    printf("The value of the expression is: %d\n", output);
}

int calculate(int op1, int op2, char operator) {
    switch (operator) {
        case '+':
            return op1 + op2;
        case '-':
            return op1 - op2;
        case '*':
            return op1 * op2;
        case '/':
            return op1 / op2;
        case '%':
            return op1 % op2;
    }
    
    if (operator == '^') {
        int result = 1;
        for (int i = 0; i < op2; i++) {
            result *= op1;
        }
        return result;
    }
    return 0;
}

See [Is it a good idea to typedef pointers](http://stackoverflow.com/questions/750178/is-it-a-good-idea-to-typedef-pointers). You should check the return from `malloc()` before using it, just in case it returns a NULL pointer. — Jonathan Leffler, Apr 24 '16 at 23:30
You might want to change "if (topPtr->nextPtr == NULL) " to if (topPtr == NULL && topPtr->nextPtr == NULL) to prevent referencing a null value. — randominstanceOfLivingThing, Apr 24 '16 at 23:30
@JonathanLeffler Sadly I am not allowed to change the typedefs. — marked-down, Apr 24 '16 at 23:31
@SureshKoya Added in a check to see if topPtr is null (`topPtr == NULL`) and it's still throwing `BAD_ACCESS`. — marked-down, Apr 24 '16 at 23:32
That happens; read the question and answers (on using typedef with pointers) anyway so you know why you shouldn't do what you're forced to do. Or write the code in terms of `StackNode` and not in terms of `StackNodePtr` — unless your hands have been tied there as well. — Jonathan Leffler, Apr 24 '16 at 23:33
The function signatures are also not allowed to be touched. Will read that Q&A though. — marked-down, Apr 24 '16 at 23:35
If the problem persists after you've ensured you've recompiled your code (after adding the `if (topPtr == NULL)` check to the start of `isEmpty()`), then you need to show us the code that is calling your stack functions. Did you write it or were you constrained to use provided test code? — Jonathan Leffler, Apr 24 '16 at 23:36
Bug: the `topPtr->nextPtr == NULL` condition in `isEmpty()` will not allow you to pop the last item. — pasztorpisti, Apr 24 '16 at 23:38
Use `head = NULL;` instead of `malloc`-ing in your `evaluatePostfixExpression()` function and remove the `topPtr->nextPtr == NULL` condition from `isEmpty()`. — pasztorpisti, Apr 24 '16 at 23:45
@pasztorpisti Done, but `BAD_ACCESS` is now occurring on the print statement inside of `printStack()`. — marked-down, Apr 24 '16 at 23:46
@EchoLogic Because `printStack()` is buggy. Your stack is empty when the head pointer is `NULL` and your `printStack()` starts by trying to access the `nextPtr` of the incoming `topPtr` without checking whether `topPtr` is `NULL`. `printStack()` should be something like `for (iter=topPtr; !isEmpty(iter); iter=iter->nextPtr) printf(whatever...);` without those `if` structures... — pasztorpisti, Apr 24 '16 at 23:50
Correct me if I'm wrong, but you malloc'd "head"... but never initialized it...!! After a successrful malloc (which you never checked ) you need to head->nextPtr = NULL; — TonyB, Apr 25 '16 at 01:00
@TonyB I think that `malloc()` simply shouldn't be there. A null pointer is perfect to represent an empty stack. — pasztorpisti, Apr 25 '16 at 01:32
@pasztorpisti I agree... but not initializing would be the reason for a segmentation violation... Initializing will not correct the implementation error... but setting "head" to NULL would. — TonyB, Apr 25 '16 at 03:17

score 0 · Answer 1 · answered Apr 25 '16 at 05:13

It looks like the expression

if (topPtr == NULL || topPtr->nextPtr == NULL)

is giving you an error because topPtr doesn't point to a valid node, nor it's null. So topPtr->nextPtr will give an error, due to the fact that topPtr is not a valid pointer.

According to your code, your head->nextPtr is not initialized to NULL, so this seems to be the cause of the problem.

By the way: Why do you initialize your head variable with an empty node? As far as I can see, you could just use head = NULL and it would work.

Last, but not least: you should free your node variable in the pop() function, in order to avoid a memory leak.

Hope it helps.

C stack implementation throws bad access error

Typedefs & definitions:

Stack operation functions

Request for context:

1 Answers1