c - 将表达式转换为后缀的程序

Question

对于在 main 中给出输入的该程序，我没有获得正确的输出 abcde-*++

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

 struct Stack{
   int capacity;
   int top;
   int *array;
 };
 struct Stack* createstack(int capacity){
     struct Stack* stack=(struct Stack*)malloc(sizeof(struct Stack));
     stack->top=-1;
     stack->capacity=capacity;
     stack->array=(int*)malloc(sizeof(int)*capacity);
     return stack;
     }
 char pop(struct Stack* stack){
     return(stack->array[stack->top--]);
 }
 void push(struct Stack* stack,char ch ){

     stack->array[++stack->top]=ch;

}
 int isempty(struct Stack* stack){

    return(stack->top==-1);
}
int isfull(struct Stack* stack){
    return(stack->top==stack->capacity-1);
}
int isfront(struct Stack* stack){
    return(stack->array[stack->top]);
}




int precedence(char ch){
    switch(ch){
      case 1: ch=='+';
      case 2: ch=='-';
         return 1;
      case 3: ch=='*';
      case 4: ch=='/';
         return 2;
      case 5: ch=='^';
         return 3;

      return-1;
    }

}
int isoperand(char ch){

    return(ch>='a'&&ch<='z'||ch>='A'&&ch<='Z');
}
void infixtopostfix(struct Stack* stack,char* exp){
       int i,k=-1;
       char res[100];
       for(i=0;exp[i];i++){
          ///if an operand is encountered
         if(isoperand(exp[i]))
            res[++k]=exp[i];
          ///if an operator is encountered
          else{
       // if(isempty(stack)||precedence(isfront(stack))<precedence(exp[i]))

        //else
            while(!isempty&&precedence(isfront(stack))>=precedence(exp[i]))
            res[++k]=pop(stack);
            push(stack,exp[i]);




         }
     }
    while(!isempty(stack))
        res[++k]=pop(stack);

        res[++k]='\0';
      printf("%s",res);

}
int main(){
struct Stack* stack=createstack(100);
char arr[100]="a+b+c*d-e";
infixtopostfix(stack,arr);
}

该程序是将表达式从中缀转换为后缀 这是算法

算法 1. 从左到右扫描中缀表达式。

如果扫描到的字符是操作数，则输出。

否则，

…..3.1 如果扫描到的运算符的优先级大于堆栈中运算符的优先级(或堆栈为空)，则将其压入。 ……

3.2 否则，将运算符从堆栈中弹出，直到扫描到的运算符的优先级小于位于堆栈顶部的运算符的优先级。将扫描到的运算符压入堆栈。

重复步骤，直到扫描到中缀表达式。

从堆栈中弹出并输出，直到堆栈不为空。 对于我的主函数中给定的输入，我没有获得正确的输出 abcde-*++

Answer 1

我不知道这些是否是您唯一的问题，但我想到了两件事:

正如 @rici 指出的，你的 precedence函数没有按照您想象的方式工作。正确的是:

int precedence(char ch){
    switch(ch){
      case '+':
      case '-':
         return 1;
      case '*':
      case '/':
         return 2;
      case '^':
         return 3;
      default: 
         return-1;
    }
}

当您检查优先级时，您有以下条件:

while(!isempty&&precedence(isfront(stack))>=precedence(exp[i]))

这永远不会起作用，因为 !isempty将始终评估为 false。您在这里询问 isempty 的地址是否函数为空。它不是。你真正想做的是检查堆栈是否为空:

while(!isempty(stack) && precedence(isfront(stack))>=precedence(exp[i]))

这将调用 isempty功能。

您确实应该学习使用调试器。单步执行您的代码将很快发现我上面指出的错误。

关于堆栈实现的一些注释。

您在pop中有一个潜在的错误。如果有人在堆栈为空时调用它，它会崩溃，因为您正在尝试访问 array[-1] ，否则会成功访问array[-1] ，并返回一个虚假值。您最好检查 top 的值，并抛出异常(或用消息使程序崩溃)，而不是返回错误值。根据客户情况调用isEmpty在调用pop之前不可靠。

您在push中有类似的错误。尝试访问超出数组范围的行为是未定义的行为。该程序可能会继续工作，也可能会崩溃。以push为例，您最终可能会推送一个随后被其他内容更改的值，然后 pop返回一个您未推送的值。

由于 pop 中的错误，你的isEmpty函数也有一个bug。如果top曾经减少到低于 -1 , isEmpty将返回false 。而不是检查 == -1 ，您应该检查 < 0 。即使您修复了 pop问题，检查 < 0更好。纵深防御。

查看堆栈顶部而不弹出堆栈的函数名称通常称为 peek ，不是isfront .