使用堆栈和C的Postfix评估

我在这里有一段时间与类似的问题，但我认为错误的问题。 为了给出一些背景知识，我的任务是创建一个C程序来解决表单中的后缀表达式

8 7 – 9 * =

我认为我的问题是，我的教授给出了一些不正确的堆栈代码。 我说这是因为我不断得到堆栈溢出（lol）错误，我的堆栈远远没有达到。 如果它有助于我使用visual studio 2005.这是我的代码：

#include  ` #include  #define STACK_SIZE 20 typedef int Bit; Bit contents[STACK_SIZE]; int top = 0; void make_empty(void); int is_empty(void); int is_full(void); void push(Bit i); int pop(void); void stack_overflow(void); void stack_underflow(void); int main(void) { Bit bit; char operation; int operand; Bit current; int result; while(scanf("%d",&current)!= '=') { push(current); } scanf("%c", &operation); while(operation != '=') { scanf("%d", &operand); printf("%d\n",top); //Pushes any number into the stack if(operand==1||operand==2||operand==3||operand==4||operand==5||operand==6||operand==7||operand==8||operand==9||operand==0) { printf("entered number loop\n"); bit = operand; if(top==20) { stack_overflow(); } push(&bit); } //Performs subtraction operation else if(operation == '-') { printf("entered minus loop\n"); if(top==1) { stack_underflow(); } result = pop() - pop(); bit = result; if(top==20) { stack_overflow(); } push(&bit); } //Performs addition operation else if(operation == '+') { if(top==1) { stack_underflow(); } result = pop() + pop(); bit = result; if(top==20) { stack_overflow(); } push(&bit); } //Performs multiplication operation else if(operation == '*') { if(top==1) { stack_underflow(); } result = pop() * pop(); bit = result; if(top==20) { stack_overflow(); } push(&bit); } //Performs division operation else if(operation == '/') { if(top==1) { stack_underflow(); } result = pop() / pop(); bit = result; if(top==20) { stack_overflow(); } push(&bit); } else if(operation == '=') { if(top==0) { stack_underflow(); } printf("%d\n",pop()); break; } } return 0; } void make_empty(void) { top = 0; } int is_empty(void) { return top == 0; } int is_full(void) { return top == STACK_SIZE; } void push(Bit i) { if (is_full()) stack_overflow(); else contents[top++] = i; } int pop(void) { if (is_empty()) stack_underflow(); else return contents[top--]; } void stack_overflow(void) { printf("Error: stack overflow!\n"); exit(EXIT_FAILURE); } void stack_underflow(void) { printf("Error: stack underflow!\n"); exit(EXIT_FAILURE); } 

现在我意识到我的代码现在有点野蛮，为此我道歉。 话虽如此，任何帮助或意见都将非常感谢，并提前感谢大家。

---

好吧，所以在考虑了所有因素之后，我想我已经接近了。 一切正常进入堆栈，一切都正常阅读。 但是，我的新实现包括将所有内容都设置为字符，然后在需要使用时转换整数。 这是我的源代码：

 #include  #include  #define STACK_SIZE 20 typedef int Bit; char contents[STACK_SIZE]; int top = 0; void make_empty(void); int is_empty(void); int is_full(void); void push(char i); char pop(void); void stack_overflow(void); void stack_underflow(void); int main(void) { char current = 'a'; char result = 'a'; char operation = 'a'; char char1; char char2; int number1; int number2; scanf("%c", &current); //While program successfully scanned a number while(current != '=') { //Performs subtraction operation if(current == '-') { printf("entered if 2\n"); char1 = pop(); number1 = char1 - '0'; printf("%d\n", number1); char2 = pop(); number2 = char2 - '0'; printf("%d\n", number2); result = number1 - number2; push(result); } //Performs addition operation else if(current == '+') { printf("entered if 2\n"); char1 = pop(); number1 = char1 - '0'; printf("%d\n", number1); char2 = pop(); number2 = char2 - '0'; printf("%d\n", number2); result = number1 + number2; push(result); } //Performs multiplication operation else if(current == '*') { printf("entered if 2\n"); char1 = pop(); number1 = char1 - '0'; printf("%d\n", number1); char2 = pop(); number2 = char2 - '0'; printf("%d\n", number2); result = number1 * number2; push(result); } //Performs division operation else if(current == '/') { printf("entered if 2\n"); char1 = pop(); number1 = char1 - '0'; printf("%d\n", number1); char2 = pop(); number2 = char2 - '0'; printf("%d\n", number2); result = number1 / number2; push(result); } else { push(current); printf("%c\n", current); } scanf(" %c", &current); } //Prints result printf("%c\n",pop()); return 0; } void make_empty(void) { top = 0; } int is_empty(void) { return top == 0; } int is_full(void) { return top == STACK_SIZE; } void push(char i) { if (is_full()) stack_overflow(); else contents[top++] = i; } char pop(void) { if (is_empty()) stack_underflow(); else return contents[top--]; } void stack_overflow(void) { printf("Error: stack overflow!\n"); exit(EXIT_FAILURE); } void stack_underflow(void) { printf("Error: stack underflow!\n"); exit(EXIT_FAILURE); } 

请记住，我一直在玩它很多，所以有随机printfs和无用的变量都用于调试目的。 每当我运行它（例如输入3 5 + =）我得到：

再说一次，请原谅我的一些杂乱的代码，因为我对C很新，但任何帮助都会很棒！

Answer 1

这是一个无限循环：

 while(scanf("%d",&current)!= '=') { push(current); } 

scanf返回成功读取的字段数。 在你的情况下，这可以是0或1.你将它与’=’比较，即ASCII 61.所以’“！=”总是正确的，你永远不会超过这个循环。

顺便说一句，如果你看看如何实现push，你会看到使用is_full（）函数检查“堆栈溢出”。 is_full（）将顶部与STACK_SIZE进行比较。 您正在比较top == 20。 你最好使用is_full。 这更抽象，即使有人更改了STACK_SIZE也能正常工作。 您甚至可以省略对top == 20和top == 0的检查，因为您唯一要做的就是调用stack_underflow / stack_overflow，这已经由pop / push函数完成。

Answer 2

我没有看到堆栈有任何问题。 但是你的主要问题至少有两个问题。

push(&bit);

push接受一个Bit ，而不是Bit * 。 你应该在这里得到一个警告，你可能已经忽略了。 不要忽视警告。

while(scanf("%d",&current)!= '=')

这绝对是错误的。 scanf返回成功输入的次数。

operand==1||operand==2||operand==3||operand==4||operand==5||operand==6||operand==7||operand==8||operand==9||operand==0

虽然这不是一个bug，你为什么要这样写？ 您可以轻松替换为：

operand >= 0 && operand <= 9

而且可能还有更多问题。

Answer 3

您遇到以下问题：

 while(scanf("%d",&current)!= '=') 

scanf函数返回扫描的项目数 ，而不是项目。 扫描%d将尝试获取整数，而不是字符。

我认为你应该更多地考虑以下事情：

 while (scanf("%d",&current) == 1) push(current); 

这将把整数推到堆栈上，直到它再也无法扫描一个（即你得到一个操作）。

这几乎肯定是你的问题，因为特定的scanf通常只返回0或1，这意味着它永远不会等于= （如果你使用的是ASCII，则为hex0x3d或十进制数61 ）。 它可以在某些情况下返回EOF ，但仍然不会给你61值。

事实上它永远不会返回61意味着它将简单地保持循环，将当前值推送到堆栈直到它溢出，这就是你所看到的行为。