c - 没有数组的堆栈的递归实现 POP 不起作用

Question

我正在尝试在不使用数组的情况下递归地实现 LIFO 堆栈。该程序接受字符串和整数作为输入，并有一些命令——即 push <int> pop empty top和quit 。

除了 pop 之外的所有内容对我来说效果很好，并且 pop仅部分起作用。如果你只弹出一个整数，那没问题，但除此之外，它会返回一个 stack is empty尽管事实并非如此。我明白为什么会发生这种情况，但我不知道如何解决它。

int stack(int top, int last) {  
  int m = read_symbol();
  if (m != READ_FAIL) {
    if (m == PUSH_SYMBOL) {
      int n = read_int();
      top = stack(n, top);
    } else if (m == POP_SYMBOL) {
      if (top == INT_MIN) {
        printf("pop error - stack is empty\n");
        top = stack(INT_MIN, INT_MIN);
      } else {
        top = stack(last, INT_MIN);
      }
    } else if (m == TOP_SYMBOL) {
      if (top == INT_MIN) {
        printf("top error - stack is empty\n");
      } else {
        printf("top - %d\n", top);
      }
      top = stack(top, last);
    } else if (m == EMPTY_SYMBOL) {
      if (top == INT_MIN) {
        printf("stack is empty\n");
      } else {
        printf("stack is not empty\n");
      }
      top = stack(top, last);
    } else if (m == QUIT_SYMBOL) {
      if (top != INT_MIN) {
        printf("quit error - stack is not empty\n");
        top = stack(top, last);
      } else {
        printf("goodbye\n");
      }
    }
  }
  return top;
}

top变量是递归返回的，所以一切正常。但是当我做类似的事情

push 1
push 2
push 3
top
pop
top
pop
top

返回的输出是

top - 3
top - 2
top error - stack is empty (SHOULD BE 1)

我尝试了各种不同的方法，但没能解决它。事实上我介绍了last参数只是为了尝试解决这个问题，即使没有 last ，其余的实现也可以正常工作。但这个参数目前似乎有效，但仅适用于一个 pop命令，因为下一个递归级别设置 last至INT_MIN然后设置为 top如果你pop再次，因此错误 stack is empty留言

任何指示或帮助将不胜感激。

编辑:INT_MIN指的是C99 limits.h INT_MIN即 -(2^32 - 1)

Answer 1

所以我想我已经解决了为什么它会这样做，首先我稍微重写了你的函数以使用切换语句来实现紧凑性(这不是你问题的解决方案):

int stack(int top, int last) {
  switch(read_symbol()) {

    // push n
    case PUSH_SYMBOL:  
      return stack(read_int(), top);

    // pop
    case POP_SYMBOL:
      if (top == INT_MIN) {
        printf("pop error - stack is empty\n");
        return stack(INT_MIN, INT_MIN);
      }

      return stack(last, INT_MIN);

    // top  
    case TOP_SYMBOL:
      if (top == INT_MIN)
        printf("top error - stack is empty\n");
      else
        printf("top - %d\n", top);

      return stack(top, last);

    // empty
    case EMPTY_SYMBOL: 
      if (top == INT_MIN)
        printf("stack is empty\n");
      else
        printf("stack is not empty\n");

      return stack(top, last);

    // quit
    case QUIT_SYMBOL:
      if (top != INT_MIN) {
        printf("quit error - stack is not empty\n");
        return stack(top, last);
      }

      printf("goodbye\n");

    case READ_FAIL: // error handling
    default:
      return top;
  }
}

然后我遵循了假定的调用堆栈:

stack(INT_MIN, INT_MIN) receives PUSH 1 -> stack(1, INT_MIN)
stack(1, INT_MIN)       receives PUSH 2 -> stack(1, 2)
stack(1, 2)             receives PUSH 3 -> stack(3, 2)
stack(3, 2)             receives TOP    -> stack(3, 2)
stack(3, 2)             receives POP    -> stack(2, INT_MIN)
stack(2, INT_MIN)       receives TOP    -> stack(2, INT_MIN)
stack(2, INT_MIN)       receives POP    -> stack(INT_MIN, INT_MIN)
stack(INT_MIN, INT_MIN) receives TOP    => ERROR

这里的问题很简单，pop调用stack(x, INT_MIN)，这在你的代码中意味着，在pop之后，堆栈的大小只有1(或零)。不使用先前调用堆栈中的数据。