Infix到后缀转换错误

Question

我正在编写一个基本程序，以便使用堆栈将infix表示法中的表达式转换为后缀符号。

这是我的节目。

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
#define  MAX_STACK_SIZE 100

//STACK IMPLEMENTATION BEGINS
struct stack{
    int top;
    char items[MAX_STACK_SIZE];
};
void push(struct stack* s, char n){
    if(s->top==MAX_STACK_SIZE-1)
        printf("Stack Overflow. Cannot push\n");
    else
        s->items[++s->top]=n;
}
bool isempty(struct stack* s){
    if(size(s)==0)
        return 1;
    else return 0;

}


char pop(struct stack* s){
 if(isempty(s))
{printf("\nStack Underflow. Cannot Pop\n");
return 0;}
else
{return (s->items[s->top--]);
}
}

bool isfull(struct stack* s){
    if(size(s)==MAX_STACK_SIZE)
        return 1;
    else return 0;

}
void display(struct stack* s){
    int num;
    if(isempty(s))
        printf("Stack empty. Nothing to display\n");
    else
    {
        for(num=0;num<=s->top;num++)
            printf("%d ",s->items[num]);
    }

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


}
//STACK IMPLEMENTATION ENDS

//checks if a character entered is an operator or not
bool isOperator(char ch){
    if(ch=='-'||ch=='+'||ch=='*'||ch=='/')
        return true;
    else
        return false;
}
//checks if a character entered is an operand(0-9) or not
bool isOperand(char ch){
    if(ch>=48 && ch<=57)
        return true;
    else
        return false;


}
//decides the precedence of operators
int precedence(char ch){
    if(ch=='*'||ch=='/')
        return 2;
    if(ch=='+'||ch=='-')
        return 1;

}
void main(){
/*
    /*Declarations Begin*/
    char infix_exp[50],ch;
    int a;    
    struct stack s;
    s.top=-1;
    /*Declarations End*/

    printf("Enter your infix expression\n");
    scanf("%s",&infix_exp);
    for(a=0;a<strlen(infix_exp);a++)//scanning the entire array
    {
        if(isOperator(infix_exp[a])){
              while(s.top>=0 && isOperator(s.items[s.top]))
            {
                  if(s.items[s.top]=='('|| isempty(&s))
                  {
                      push(&s,infix_exp[a]);

                  }
                  if(isOperator(s.items[s.top])){
                      while((s.top--)>=0){
                      if(precedence(infix_exp[a])>=precedence(s.items[s.top]))
                      {
                          ch=pop(&s);
                           printf("%c",ch);

                         push(&s,infix_exp[a]);  
                      }
                      else
                      {
                           push(&s,infix_exp[a]);  
                      }}}}}
        if(isOperand(infix_exp[a])){printf("%c",infix_exp[a]);}
        if(infix_exp[a]=='('){push(&s,'(');}
        if(infix_exp[a]==')'){
             while(s.top>=0 && s.items[s.top]!='(')
            {
                ch=pop(&s);
                printf("%c",ch);

            }
            pop(&s);
        }}}

这是输出。

Enter your infix expression
6+1
61
RUN FINISHED; exit value 3; real time: 4s; user: 0ms; system: 0ms

我遵循的逻辑是这样的。

用户输入表达式后，程序将扫描每个元素。如果元素是操作数，则打印它。如果元素是一个开口括号，则将其推到堆栈上。如果元素是一个结束括号，则会弹出堆栈中的每个元素并打印出来，直到遇到相应的开口括号为止。如果元素是一个运算符(由isOperator()函数检查)，那么堆栈的顶部元素可以是这三个元素之一，

1. 打开支架-元素被简单地推到堆栈上；
2. Null，即堆栈是空的-元素被简单地推到堆栈上；
3. 另一个操作符-然后遍历堆栈，infix表达式元素的优先级(precedence())大于或等于堆栈顶部元素的优先级，然后弹出堆栈顶部并推送infix表达式元素。否则，只会推送infix表达式元素，就不会弹出任何内容。

我无法得到输出中的操作符。错误可能是什么？我可能是一个微不足道的人，也许是通过价值的打印，也可能是因为我的逻辑。任何帮助都很感激。

Answer 1

看起来您使用的是调车码算法，但是有一些事情是不正确的。

首先，在算法的内容运行之后，您仍然必须打印堆栈的其余内容，并检查不匹配的父类。正如维基的文章所说：

1. 当没有更多的标记可读时
2. 当堆栈中仍然存在操作符标记时：
   • 如果堆栈顶部的运算符令牌是括号，那么就会出现不匹配的括号。
   • 将操作符弹出到输出队列中。

​

这很容易添加到代码中，只需在for循环之后添加如下内容：

while(!isempty(&s))
{
    ch = pop(&s);
    if(ch == ')' || ch == '(') {
        printf("\nMismatched parens\n");
        break;
    }
    printf("%c",ch);
}

但这不能马上解决问题，因为还有另外一个问题。

第二个问题是当前输入令牌是运算符的情况，您可以这样说：

如果元素是一个运算符(由isOperator()函数检查)，那么堆栈的顶部元素可以是以下三个元素之一，

1. 打开支架-元素被简单地推到堆栈上；
2. Null，即堆栈是空的-元素被简单地推到堆栈上；
3. 另一个操作符-然后遍历堆栈，infix表达式元素的优先级(优先级())大于或等于堆栈顶部元素的优先级，然后弹出堆栈顶部，然后printed.and将infix表达式元素推送。否则，只会推送infix表达式元素，就不会弹出任何内容。

这个描述基本上是正确的，只不过我认为您的优先级是向后的，并且您应该只在最后推到输出队列一次(而不是对堆栈中的每个元素进行一次)。

但你的代码不匹配。

下面是包含注释的代码的相关部分

//if the input token is an operator
if(isOperator(infix_exp[a]))
{
    //while s isn't empty and has an operator on top
    while(s.top>=0 && isOperator(s.items[s.top]))
    {
        //if the top element is a '(' (NEVER HAPPENS because '(' isn't an operator)
        if(s.items[s.top]=='('|| isempty(&s))
        {
            push(&s,infix_exp[a]);
        }
        //If the top element is an operator (ALWAYS HAPPENS)
        if(isOperator(s.items[s.top]))
        {
            //discard the top element of the stack, loop while there are still elements left
            while((s.top--)>=0)
            {
                //if the top element of the stack (after the one that was discarded) has precedence
                //then pop it to the output queue and push the input token to the stack
                if(precedence(infix_exp[a])>=precedence(s.items[s.top]))
                {
                    ch=pop(&s);
                    printf("%c",ch);
                    push(&s,infix_exp[a]);  
                }
                //otherwise push the input token to the stack
                else {                
                    push(&s,infix_exp[a]);  
                }
            }
        }
    }
}

请注意，其中一个if语句从未被触发。您有两个while循环要在堆栈上迭代，其中一个实际上不进行任何迭代。在第二个while循环中，可以将堆栈缩小到两个不同的位置。并且可以多次将输入令牌推送到输出。

总之，这只是一大团乱。

现在，让我们看看算法(同样根据维基百科)说要做什么(对糟糕的格式表示抱歉)：

1. 如果令牌是一个操作符o1，那么：
2. 在堆栈顶部有一个运算符令牌，o2，以及 或者o1是左结合的，它的优先级等于o2的优先级。 或者o1的优先级小于o2，

- pop o2 off the stack, onto the output queue.

​

1. 将o1推到堆栈上。

这与上面的代码并不完全匹配，但又会是什么呢？

第一部分是对的

//if the input token is an operator
if(isOperator(infix_exp[a]))
{

然后，您需要使用循环检查来查看堆栈顶部是否有一个具有适当优先级的操作符：

    //Traverse stack while the precedence is right
    while(!isempty(&s) && isOperator(s.items[s.top])
          && (precedence(infix_exp[a]) <= precedence(s.items[s.top])) )
    {

从循环中弹出：

        ch = pop(&s);
        printf("%c",ch);
    }

最后，将输入令牌推到堆栈上：

    push(&s, infix_exp[a]);
}