#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, 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 = s->base + s->stackSize;
        s->stackSize = s->stackSize + STACKINCREMENT;
    }
    
    *(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 != '#' )
    {
        //判断位数，例如判断1或者11，如果输入的是0~9，则直接打印，然后接一个scanf，判断下一个输入的是数字还是符号，数字就继续输出，符号就输出空格
        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 )
        {
            //如果是空栈，则直接push，记录这个符号
            if( !StackLen(s) )
            {
                Push(&s, c);
            }
            //如果栈内已经有符号了，先把符号拿出来
            else
            {
                do
                {
                    Pop(&s, &e);
                    if( '(' == e )  //如果取出来的是括号，那就继续入栈，因为入的是括号内的符号
                    {
                        Push(&s, e);
                    }
                    else  //如果取出来的不是括号，那就先把这个符号输出，因为遇到新符号了
                    {
                        printf("%c ", e);
                    }
                }while( StackLen(s) && '('!=e );  //然后判断栈是不是还有东西，并且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);
    }
    
    return 0;
}