C语言 没有数组的堆栈的递归实现 POP 不起作用

Question

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

除了pop之外，一切都对我来说很好，pop只能部分工作。如果您只弹出一个 int 也没关系，但除此之外，即使它不是，它也会返回我一个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 emptyn");
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 emptyn");
} else {
printf("top - %dn", top);
}
top = stack(top, last);
} else if (m == EMPTY_SYMBOL) {
if (top == INT_MIN) {
printf("stack is emptyn");
} else {
printf("stack is not emptyn");
}
top = stack(top, last);
} else if (m == QUIT_SYMBOL) {
if (top != INT_MIN) {
printf("quit error - stack is not emptyn");
top = stack(top, last);
} else {
printf("goodbyen");
}
}
}
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，如果您再次pop，则设置为top， 因此，错误的stack is empty消息

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

编辑：INT_MIN是指C99limits.hINT_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 emptyn");
return stack(INT_MIN, INT_MIN);
}
return stack(last, INT_MIN);
// top  
case TOP_SYMBOL:
if (top == INT_MIN)
printf("top error - stack is emptyn");
else
printf("top - %dn", top);
return stack(top, last);
// empty
case EMPTY_SYMBOL: 
if (top == INT_MIN)
printf("stack is emptyn");
else
printf("stack is not emptyn");
return stack(top, last);
// quit
case QUIT_SYMBOL:
if (top != INT_MIN) {
printf("quit error - stack is not emptyn");
return stack(top, last);
}
printf("goodbyen");
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(或零)。不使用上一个调用堆栈中的数据。

Answer 2

inside else if (m == POP_SYMBOL) { } change

if (top == INT_MIN) 

自

if (top < INT_MIN) 

让我知道它是否适合您，因为它可能会因为变量"top"的逻辑不正确而发生，例如，我们可能会在我们的逻辑中认为变量"top"被破坏了，而实际上它会在下一次迭代中被破坏。这对您不起作用，然后发布 INT_MIN 的值(可能是 #define 个 - ed 值)