0

对于大学作业的一个组件，我们必须实现一个堆栈，我认为我已经做得足够好了，它可以正常工作。当我自己测试堆栈时，它似乎工作正常，但是当我将它用作我的解决方案的一部分时，它的行为不同，我不知道为什么。有人可以指出我的错误吗？谢谢。

编辑：我能感觉到很多“它的行为有何不同？” 评论正在路上，所以这就是我注意到的。在运行 的测试堆栈部分时main，所有操作都执行并打印得非常好，但是当我运行的第二部分main并注释掉测试部分时，当我试图推入堆栈时程序崩溃 - 某事以前没有失败。

主程序

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

struct stackNode {
    char data;
    struct stackNode *nextPtr;
};
typedef struct stackNode StackNode;
typedef StackNode *StackNodePtr;

typedef enum {
    false, true
} t_bool;

void* emalloc(size_t s) {
    void* p = malloc(s);
    if (NULL == p) {
        fprintf(stderr, "Memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }
    return p;
}

void print_array(char* array, size_t n){
    int i;
    printf("[");
    for(i = 0; i < n - 1; i++){
        printf("%c, ", array[i]);
    }
    printf("%c]\n", array[i]);
}


// Determine if c is an operator.
int isOperator(char c) {
    char ops [6] = {'+', '-', '*', '/', '%', '^'};
    int i;
    for (i = 0; i < 6; i++)
        if (ops[i] == c) return true;
    return false;
}

int op_priority(char c) {
    if (c == '+' || c == '-') return 0;
    else if (c == '*' || c == '/') return 1;
    else if (c == '^' || c == '%') return 2;
    return -1;
}


// Determine if the precedence of operator1 is less than, equal to, or greater than
// the precedence of operator2. The function returns -1, 0 and 1, respectively.
int precedence(char op1, char op2) {
    int op1_p = op_priority(op1);
    int op2_p = op_priority(op2);
    if (op1_p < op2_p) return -1;
    else if (op1_p > op2_p) return 1;
    else return 0;
}





// Push a value on the stack.
void push(StackNodePtr *topPtr, char value) { 
    StackNodePtr temp = (StackNodePtr) emalloc(sizeof (StackNode));
    temp->data = value;
    temp->nextPtr = *topPtr;
    *topPtr = temp;
}

// Pop a value off the stack. 
char pop(StackNodePtr *topPtr) {
    StackNodePtr t = *topPtr;
    if (NULL != *topPtr) {
        char c = t->data;
        *topPtr = t->nextPtr;
        free(t);
        return c;
    } else {
        printf("Stack is empty.\n");
        return '\0';
    }
}

// Return the top value of the stack without popping the stack.
char peek(StackNodePtr topPtr) {
    if (NULL != topPtr) {
        return topPtr->data;
    } else {
        printf("Stack is empty.\n");
    }
}

// Determine if the stack is empty.
int isEmpty(StackNodePtr topPtr) {
    if (NULL == topPtr) return true;
    return false;
}

// Prints the stack
void printStack(StackNodePtr topPtr) {
    if (!isEmpty(topPtr)){

    StackNodePtr t = topPtr;
    while (NULL != t) {
        printf("%c\t", t->data);
        t = t->nextPtr;
    }
    printf("NULL\n");
    } else {
       printf("Stack is empty.\n");
    }
}

// Convert the infix expression to postfix notation.
void convertToPostfix(char infix [], char postfix [], int expression_length) {
    printf("At top of cnvToPostfix\n");
    int infix_count = 0;
    int postfix_count = 0;

    ////////////////////////////////////////////
    StackNodePtr *stack;
    push(stack, '(');
    printStack(*stack);
    ////////////////////////////////////////////

    infix[expression_length] = ')';
    while (isEmpty(*stack)) {
        char current = infix[infix_count++];
        if (isdigit(current)) {
            postfix[postfix_count++] = current;
        } else if (current == '(') {
            push(stack, current);
        } else if (isOperator(current)) {
            while (true) {
                char top = peek(*stack);
                if (isOperator(top) && precedence(current, top) >= 0) {
                  postfix[postfix_count++] = pop(stack);
                } else {
                    break;
                }
            }
            push(stack, current);
        }
        else if (current == ')') {
            while (true) {
                char top = peek(*stack);
                if (top == '(') {
                    pop(stack);
                    break;
                } else {
                     postfix[postfix_count++] = pop(stack);
                }
            }
        }
    }
}


int main() {

    printf("Testing stack\n");
    printf("Pushing 1, 2, and 3 onto stack, peeking and popping.\n");
    StackNodePtr *stack;
    push(stack, '1');
    push(stack, '2');
    push(stack, '3');
    printf("Printing stack\n\n");
    printStack(*stack);
    printf("Peek: %c\n", peek(*stack));
    printf("Pop: %c\n", pop(stack));
    printf("Printing stack\n");
    printStack(*stack);


/*
    printf("Enter the infix expression.\n");

    char c;
    char infix [1024];
    int count = 0;
    while ((scanf("%c", &c)) == 1) {
        if ((int) c == 10) break;
        infix[count++] = c;
    }

    printf("The original infix expression is:\n");
    print_array(infix, count);


    char postfix [count];

    convertToPostfix(infix, postfix, count);
    printf("The expression in postfix notation is:\n");
    print_array(postfix, count);
*/
     return 0;
}
4

2 回答 2

4

我看到至少一个直接的问题：

StackNodePtr *stack;
push(stack, '1');

您的堆栈的初始化在哪里？使用未初始化的指针是即时的“未定义行为”领域。

如果您仔细查看您的push代码，您会看到它在当前项目之前插入新项目，但将新项目的nextPtr指针设置为前一个（未初始化的）值。

这意味着，堆栈中的最后一项实际上不会指向 NULL。

于 2012-05-09T03:25:01.243 回答
2

你并没有真正初始化你的堆栈：

StackNodePtr *stack;
push(stack, '(');

StackNodePtr作为指针类型和指向该类型的指针也可能令人困惑stack。您需要清楚在每种可能的用法中应该应用多少级间接。

首先，想象一下首先将新堆栈传递给isEmpty：

StackNodePtr *stack;
printf("%d\n", isEmptypush(*stack));

isEmpty它传递的值会做什么？

我认为你想要的是：

StackNodePtr stack = NULL;
push(&stack, '(');

该函数中的其他用途stack也应类似地从*stacktostack或stackto更改为&stack。

于 2012-05-09T03:33:31.813 回答