论坛 › 数据结构与算法 › 中缀表达式转后缀表达式

夏季的春秋 发表于 2023-6-7 12:18:38

中缀表达式转后缀表达式

中缀表达式转后缀表达式，在编译器上运行是好的，但是提交到oj上就一直是输出超限，想知道怎么解决？
下面上代码
#include <stdio.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10

typedef char ElemType;
typedef struct
{
    ElemType *base;
    ElemType *top;
    int stacksize;
}sqstack;

void initstack(sqstack *s)
{
    s->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
    if(!s->base)
    {
      exit(0);
    }
    s->top=s->base;
    s->stacksize=STACK_INIT_SIZE;
}

void push(sqstack *s,char e)
{
    if(s->top-s->base>=s->stacksize)
    {
      s->base=(ElemType *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(ElemType));
      if(!s->base)
      {
            exit(0);
      }
      s->top=s->base+s->stacksize;
      s->stacksize=s->stacksize+STACKINCREMENT;
    }

    *(s->top)=e;
    s->top++;
}

void pop(sqstack *s,char *e)
{
    if(s->top==s->base)
    {
      return;
    }

    *e=*--(s->top);
}

int stacklen(sqstack s)
{
    return (s.top-s.base);
}

int main(void)
{
    sqstack s;
    char c,e;

    initstack(&s);

    while((scanf("%c",&c))!=EOF)
    {
      while((c>='A'&&c<='Z')||(c>='a'&&c<='z'))
      {
            printf("%c",c);
            scanf("%c",&c);
      }

      if(')'==c)
      {
            pop(&s,&e);
            while('('!=e)
            {
                printf("%c",e);
                pop(&s,&e);
            }
      }

      else if('+'==c||'-'==c)
      {
            if(!stacklen(s))
            {
                push(&s,c);
            }
            else
            {
                do
                {
                  pop(&s,&e);
                  if('('==e)
                  {
                        push(&s,e);
                  }
                  else
                  {
                        printf("%c",e);
                  }
                }while(stacklen(s)&&'('!=e);
                push(&s,c);
            }
      }
      else if(c=='*'||c=='/')
      {
            pop(&s,&e);
            if(e=='*'||e=='/')
            {
                printf("%c",e);
            }
            else
            {
                push(&s,e);
            }
            push(&s,c);
      }
      else if(c=='(')
      {
            push(&s,c);
      }
      else if('\n'==c)
      {
            break;
      }
      else
      {
            return -1;
      }
    }

    while(stacklen(s))
    {
      pop(&s,&e);
      printf("%c",e);
    }

    return 0;
}

isdkz 发表于 2023-6-7 12:18:39

看起来这个程序用于将中缀表达式转换为后缀表达式。如果你在提交到在线编程环境（Online Judge）时遇到了输出超限的问题，这可能是由于程序输出了比预期更多的数据，或者程序陷入了无限循环。

一种可能的原因是，对于每一个字符，如果它不是字母，'+'，'-'，'*'，'/'，'('，')'，或者'\n'，程序会返回-1并结束，这可能是在处理空格或者其他不在预期中的字符时出现问题。如果输入中包含这些字符，程序可能会意外结束，或者在处理之前的循环中陷入无限循环。

另一种可能的原因是，这个程序没有考虑到优先级更高的运算符在优先级较低的运算符之前的情况。例如，对于表达式 a+b*c ，这个程序会生成后缀表达式 abc*+ ，这是正确的。但是对于表达式 a*b+c ，这个程序会生成 ab*c+ ，这是错误的，正确的后缀表达式应该是 ab*c+ 。这是因为在处理'+'时，程序应该将栈中所有的运算符都弹出，直到遇到了'('或者栈为空。

为了解决这些问题，你可能需要做以下修改：

1. 添加一个条件来处理空格字符，忽略它们而不是结束程序。

2. 在处理运算符的优先级时，应该考虑到所有的情况，不仅仅是当前运算符比栈顶运算符的优先级更高的情况。你可能需要写一个函数来比较两个运算符的优先级，然后在处理运算符时使用这个函数。

夏季的春秋 发表于 2023-6-7 16:54:04

isdkz 发表于 2023-6-7 12:22
看起来这个程序用于将中缀表达式转换为后缀表达式。如果你在提交到在线编程环境（Online Judge）时遇到了输 ...

我在输入乘和除加了个判断栈是否为空，现在是82%，想问还差18%怎么改

isdkz 发表于 2023-6-7 16:56:04

夏季的春秋 发表于 2023-6-7 16:54
我在输入乘和除加了个判断栈是否为空，现在是82%，想问还差18%怎么改

如果你的程序已经通过了82%的测试用例，那么你已经成功地处理了大多数情况。下面是一些可能影响程序正确性的问题，可以帮助你找出剩下的问题：

1. 优先级判断: 在处理'+'和'-'运算符时，你的程序会将栈中所有的运算符都弹出，直到遇到'('。这意味着，如果输入是 a*b+c ，程序会生成 ab*c+ ，这是正确的。但是，如果输入是 a+b*c ，程序也会生成 abc*+ ，这是错误的，正确的后缀表达式应该是 ab+c* 。这是因为'+'的优先级低于'*'。在这个例子中，你需要修改你的程序，使其只在当前运算符的优先级高于或等于栈顶运算符的优先级时，才将栈顶运算符弹出。

2. 非法字符: 确保你的程序能够正确处理所有非法字符。你的程序应该能够处理所有可能出现的字符，而不只是'A'到'Z'，'a'到'z'，'+'，'-'，'*'，'/'，'('，')'和'\n'。

3. 空格和换行符: 你的程序应该能够忽略输入中的空格和换行符。在当前的程序中，如果输入中包含空格，程序可能会提前结束。

4. 错误的输入: 确保你的程序能够处理错误的输入。例如，如果输入的表达式中包含不匹配的括号，或者包含非法的字符，你的程序应该能够检测到这些错误。

如果这些建议不能帮助你找出问题，你可能需要更详细地检查你的程序，或者用更多的测试用例来测试它。

夏季的春秋 发表于 2023-6-7 21:02:37

isdkz 发表于 2023-6-7 16:56
如果你的程序已经通过了82%的测试用例，那么你已经成功地处理了大多数情况。下面是一些可能影响程序正确 ...

这第一个优先级判断a+b*c的a+b应该加括号把，不然不是后面的那个后缀表达式

夏季的春秋 发表于 2023-6-9 15:07:47

终于想出来了，上代码#include <stdio.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10

typedef char ElemType;
typedef struct
{
    ElemType *base;
    ElemType *top;
    int stacksize;
}sqstack;

void initstack(sqstack *s)
{
    s->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
    if(!s->base)
    {
      exit(0);
    }
    s->top=s->base;
    s->stacksize=STACK_INIT_SIZE;
}

void push(sqstack *s,char e)
{
    if(s->top-s->base>=s->stacksize)
    {
      s->base=(ElemType *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(ElemType));
      if(!s->base)
      {
            exit(0);
      }
      s->top=s->base+s->stacksize;
      s->stacksize=s->stacksize+STACKINCREMENT;
    }

    *(s->top)=e;
    s->top++;
}

void pop(sqstack *s,char *e)
{
    if(s->top==s->base)
    {
      return;
    }

    *e=*--(s->top);
}

int stacklen(sqstack s)
{
    return (s.top-s.base);
}

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

int main(void)
{
    sqstack s;
    char c,e;

    initstack(&s);

    while((scanf("%c",&c))!=EOF)
    {
      if((c>='A'&&c<='Z')||(c>='a'&&c<='z'))
      {
            printf("%c",c);
      }

      else
      {
            if(c=='(')
                {
                  push(&s,c);
                }
            else if(')'==c)
            {
                pop(&s,&e);
                while(('('!=e)&&(stacklen(s)!=0))
                        {
                            printf("%c",e);
                            pop(&s,&e);
                        }
            }
            else if('+'==c||'-'==c)
                {
                  if(!stacklen(s))
                  {
                        push(&s,c);
                  }
                  else
                  {
                        do
                            {
                              pop(&s,&e);
                              if('('==e)
                                    {
                                        push(&s,e);
                                    }
                              else
                                    {
                                        printf("%c",e);
                                    }
                            }while(stacklen(s)&&'('!=e);
                        push(&s,c);
                     }
                  }
            else if(c=='*'||c=='/')
                {
                     if(!stacklen(s))
                        {
                            push(&s,c);
                        }
                     else if(c=='*'||c=='/')
                        {
                            pop(&s,&e);
                            if('*'==e||'/'==e)
                            {
                              printf("%c",e);
                            }
                            else
                            {
                              push(&s,e);
                            }
                            push(&s,c);
                        }
                }

            else if('\n'==c)
                {
                  break;
                }
            else
                {
                  exit(0);
                }
      }
    }

    while(stacklen(s))
    {
      pop(&s,&e);
      printf("%c",e);
    }

    return 0;
}

查看完整版本: 中缀表达式转后缀表达式