C 堆栈实现抛出错误访问错误

Question

正在用 C 构建堆栈。堆栈有时会失败，并在我的 isEmpty() 函数中进行 if 检查时出现 EXC_BAD_ACCESS 错误，我不确定原因。

类型定义和定义:

#define NodeSize sizeof(StackNode)

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

typedef struct stackNode StackNode;
typedef StackNode *StackNodePtr;

堆栈操作函数

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;
}

即使只是正确方向的提示，我们也将不胜感激。

请求上下文:

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;
}

Answer 1

看起来像这个表达式

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

给你一个错误，因为 topPtr 没有指向有效的节点，也不是空的。因此，topPtr->nextPtr 将给出错误，因为 topPtr 不是有效的指针。

根据您的代码，您的 head->nextPtr 未初始化为 NULL，因此这似乎是问题的原因。

顺便问一下:为什么用空节点初始化 head 变量？据我所知，您只需使用 head = NULL 就可以了。

最后但并非最不重要的一点:您应该在 pop() 函数中释放 node 变量，以避免内存泄漏。

希望有帮助。