中缀表达式转后缀表达式

梅祥

#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