使用堆栈的中缀到后缀转换显示无限循环

Question

下面是使用 stack.The 代码执行无限循环打印 stack underflow 的中缀到后缀转换的代码 pop 函数之一，我试过评论 pop右括号循环中的函数调用但是没有输出，我无法找到哪个 pop 函数导致了这个问题。如果有人能帮我找出问题所在，我们将不胜感激。

P.S。 - 如果我从传递的中缀方程中删除括号，代码工作正常。

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

struct stack{
    int size;
    int top;
    char *arr;
};

void display(struct stack *ptr)
{
    if(ptr->top == -1)
    {
        printf("Stack is Empty");
    }
    
    else
    {
        for(int i = ptr->top ; i>=0 ; i--)
        {
            printf("Element: %d\n",ptr->arr[i]);
            
        }
    }
}

int isEmpty(struct stack *ptr)
{
    if(ptr->top == -1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int isFull(struct stack *ptr)
{
    if(ptr->top == ptr->size - 1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

void push(struct stack *ptr,int data)
{
    if(isFull(ptr))
    {
        printf("Stack Overflow");
    }
    else
    {
        ptr->top = ptr->top + 1;
        ptr->arr[ptr->top] = data;
    }    
}

char pop(struct stack *ptr)
{
    if(isEmpty(ptr))
    {
        printf("Stack Underflow");
        return 0;
    }
    else
    {
        char ch = ptr->arr[ptr->top];
        ptr->top = ptr->top - 1;
        return ch;

    }    
}

char stackTop(struct stack *ptr)
{
    return ptr->arr[ptr->top];
}

int isOperator(char a)
{
    if(a == '+'|| a == '-'|| a == '*'|| a == '/')
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int precedence(char a)
{
    if(a == '*' || a == '/')
    {
        return 3;
    }
    else if(a == '+' || a == '-')
    {
        return 2;
    }
    else
    {
        return -1;
    }
}

char* infix_postfix(char *infix)
{
    struct stack *sp = (struct stack *) malloc(sizeof(struct stack));

    sp->size = 100;
    sp->top = -1;
    sp->arr = (char *) malloc(sp->size * sizeof(char));
    char *postfix = (char *) malloc((strlen(infix+1)) * sizeof(char));

    int i=0; 
    int j=0;
    
    while(infix[i] != '[=10=]')
    {
        if(infix[i] == '(')
        {
            push(sp,infix[i]);
            i++;
        }
        else if(infix[i] == ')')
        {
            while(!(isEmpty(sp)) && stackTop(sp) != '(')
            {
                postfix[j] = pop(sp);
                j++;
            }
      
            pop(sp);
               
        }
        else if(!isOperator(infix[i]))
        {
            postfix[j] = infix[i];
            i++;
            j++;
        }
        else
        {
            while(!(isEmpty(sp)) && precedence(infix[i])<=precedence(stackTop(sp)))
            {
                postfix[j] = pop(sp);
                j++;
                
            }
            
            push(sp,infix[i]);
            i++;
            
        }
    }
    while(!isEmpty(sp))
    {
        postfix[j] = pop(sp);
        j++;
    }

    postfix[j] = '[=10=]';
    return postfix;
}

int main(void)
{
    char *infix = "(x-y/z-k*d)";

    printf("postfix is %s",infix_postfix(infix));

    return 0;
}

Answer 1

代码卡在 ')'。

在 else if(infix[i] == ')') { .... } 块中的某处添加 i++; 结果如下。 Else代码继续解析')'.

postfix is xyz/-kd*-

如何发现错误：

添加了调试打印。

while (infix[i] != '[=11=]') {
  printf("Infix: %d %c\n", infix[i], infix[i]);  // added

这导致在解析 ')' 时看到代码卡住了。

使用堆栈的中缀到后缀转换显示无限循环

infix to postfix conversion using stack shows an infinite loop

c

stack

infix-notation

postfix-notation

data-structures