#include <stdio.h>
#include <stdlib.h>
#include <ctype.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,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++;
}
void pop(sqStack *s,ElemType *e){
    if( s->top == s->base){
        return;
    }
    *e = *--(s->top);
}
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");
            return -1;
        }
        scanf("%c",&c);
    }
    while( Stacklen(s) ){
        pop(&s,&e);
        printf("%c ",e);
    }
    return 0;
}