c - 使用堆栈将中缀转换为后缀

Question

我的讲师给了我一个作业，要求我创建一个程序，使用 Stack 将中缀表达式转换为后缀表达式。我已经创建了堆栈类和一些函数来读取中缀表达式。

但是这个名为 inToPos(char string[]) 的函数负责使用堆栈将字符串 inFix 中的 inFix 表达式转换为字符串 postFix 中的后修复表达式，它正在创建一个断点。你们能帮帮我并告诉我我做错了什么吗？

这些是我的代码，非常需要您的帮助..:)

#include<stdio.h>
#include<stdlib.h>
#define MAX 15
#define true 1 
#define false 0 

typedef struct node* nodeptr;

typedef struct node{
    int data;
    nodeptr next;
}Node;

typedef struct{
    int count;
    nodeptr top;
}Stack;
typedef Stack* StackList;

StackList create();
void display(StackList list);
int isEmpty(StackList list);
void push(StackList list, int item);
void pop(StackList list);

int inToPos(char string[]);
int isOperator(char string[], int i);
int precedence(char x);

StackList create(){
StackList list;
list=(StackList)malloc(sizeof(Stack));
list->count=0;
list->top=NULL;
return list;
}

void display(StackList list){
    nodeptr ptr;
    ptr=list->top;
    while(ptr!=NULL){
        printf("%d ",ptr->data);
        ptr=ptr->next;
    }
    printf("\n");
}

int isEmpty(StackList list){
    return list->count==0;
    //return list->top==NULL;
}

void push(StackList list, int item){
    nodeptr temp;
    temp=(nodeptr)malloc(sizeof(Node));
    temp->data=item;
    temp->next=list->top;
    list->top=temp;
    (list->count)++;
}

void pop(StackList list){
    nodeptr temp;
    temp=list->top;
    list->top=temp->next;
    temp->next=NULL;
    free(temp);
    (list->count)--;
}

int inToPos(char string[]){
    int i,a=0;
    char postfix[MAX];
    StackList list=create();
    for(i=0;string[i]!='\0';i++){
        if(!isOperator(string,i)){
            postfix[a]=string[i];
            a++;
        }
        else if(isEmpty(list))
            push(list,string[i]);
        else{
            if(precedence(string[i])>precedence(list->top->data))
                push(list,string[i]);
            else{
                postfix[a]=list->top->data;
                a++;
                pop(list);
                if(!isEmpty(list)){
                    while(precedence(list->top->data)<=precedence(string[i])){
                        postfix[a]=list->top->data;
                        a++;
                        pop(list);
                    }
                }
                else
                    push(list,string[i]);
            }
        }
    }
    puts(postfix);
}


int isOperator(char string[], int i){
    switch(string[i])
    {
    case '+':
    case '-':
    case '*':
    case '%':
    case '/': return true;

    default: return false;
    }
}

int precedence(char x){
    switch(x)
    {
    case '%':
    case '*':
    case '/': return 2;
    case '+':
    case '-': return 1;

    default: return 0;
    }
}
int main(void){

    char string[MAX]="a+b*c-d";
    inToPos(string);
}

请注意，函数 inToPos 是使用此算法创建的:

• 从左到右扫描中缀字符串。
• 初始化一个空堆栈。
• 如果扫描到的字符是操作数，则将其添加到后缀字符串中。 如果扫描到的字符是运算符并且堆栈为空 将角色插入堆栈。
• 如果扫描到的字符是运算符并且堆栈不为空， 将字符的优​​先级与上面的元素进行比较 堆栈(topStack)。如果 topStack 的优先级高于 扫描到的字符 弹出堆栈 else 将扫描到的字符压入 堆。只要 stack 不为​​空且 topStack 重复此步骤 优先于角色。重复此步骤直至 字符被扫描。
• (扫描完所有字符后，我们必须添加任何符合条件的字符 堆栈可能有后缀字符串。)如果堆栈不为空，则添加 topStack 到 Postfix 字符串并弹出堆栈。重复此步骤 只要堆栈不为空即可。
• 返回后缀字符串。

Answer 1

您确实应该学习如何使用调试器，它是解决此类问题的绝佳工具。但是，我运行了它并找出了你的问题:

在这一行:

while(precedence(list->top->data)<=precedence(string[i])){

当你迭代列表时，你需要每次都检查堆栈是否为空，而不仅仅是在进入循环之前。所以，做这样的事情:

while(!isEmpty(list) && precedence(list->top->data)<=precedence(string[i])){

相反。