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

梅祥 发表于 2019-8-24 22:29:07

中缀表达式转后缀表达式

#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;

int 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;
        return 0;
}

int push(sqstack *s,ElemType 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)=e;
        s->top++;
        return 0;
}

int pop(sqstack *s,ElemType *e)
{
        if(s->top==s->base)
        {
                return 0;
        }
        *e=*(--s->top);
        return 0;
}

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

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

    Initstack( &s );

    printf("请输入中缀表达式，以#作为结束标志：");
    scanf("%c", &c);

    while( c != '#' )
    {
      while( c>='0' && c<='9' )
      {
            printf("%c", c);
            scanf("%c", &c);
            if( c<'0' || c>'9' )
            {
                printf(" ");
            }
      }

      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 || '('==c )
      {
            push(&s, c);
      }
      else if( '#'== c )
      {
            break;
      }
      else
      {
            printf("\n出错：输入格式错误！\n");
            return -1;
      }

      scanf("%c", &c);
    }

    while( stackLen(s) )
    {
      pop(&s, &e);
      printf("%c ", e);
    }
    printf("\n");
    return 0;
}

zsszss 发表于 2020-4-7 11:31:31

{:10_249:}

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