программа для преобразования выражения в постфикс

Question

Я не получаю правильный вывод для этой программы, получая как abcde - * ++ для ввода данных в main

 #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. Сканируйте выражение инфикса слева направо.

2. Если отсканированный символ является операндом, выведите его.

3. прочее

… ..3.1 Если приоритет сканируемого оператора больше приоритета оператора в стеке (или стек пуст), нажмите его. ... ..

3.2 Иначе, выталкивать оператор из стека до тех пор, пока приоритет отсканированного оператора не станет меньше приоритета оператора, находящегося на вершине стека. Поместите сканированный оператор в стек.

6. Повторяйте шаги до тех пор, пока не будет отсканировано инфиксное выражение.
7. Поп и выход из стека, пока он не будет пустым. я не получаю правильный вывод, получая как 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 также содержит ошибку. Если top когда-либо уменьшится ниже -1, isEmpty вернет false. Вместо проверки на == -1, вы должны проверить на < 0. Даже если вы решите проблему pop, проверка на < 0 лучше. Глубокая защита.

Имя функции, которая смотрит на вершину стека, не выталкивая ее, обычно называется peek, а не isfront.