0

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

这是我的程序。

#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. 另一个运算符 - 然后遍历堆栈，并且中precedence()缀表达式元素的优先级（）大于或等于堆栈顶部元素的优先级，然后弹出并打印堆栈顶部。并推送中缀表达式元素。否则只推送中缀表达式元素，不弹出任何内容。

我无法在输出中获取运算符。可能是什么错误？我可能是一个微不足道的人，可能是打印值，也可能是我的逻辑。任何帮助表示赞赏。

4

1 回答 1

1

看起来您正在使用Shutting-yard algorithm，但是您做错了一些事情。

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

  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. 另一个运算符 - 然后遍历堆栈并且中缀表达式元素的优先级（precedence（））大于或等于堆栈顶部元素的优先级然后弹出并打印堆栈顶部。并且中缀表达式元素被推送. 否则只推送中缀表达式元素，不弹出任何内容。

这个描述基本上是正确的，除了我认为你的优先级倒退了，你应该只在最后推送一次输出队列（而不是堆栈中的每个元素一次）。

但是您的代码与它不匹配。

这是带有注释注释的代码的相关部分

//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，

    • 将 o2 从堆栈中弹出到输出队列中。

  3. 将 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]);
}
于 2013-09-01T20:30:07.210 回答