#include <stdio.h>
#define MaxSize 50

typedef struct{
    char data[MaxSize];
    int top;
}SqStack;


void InitStack(SqStack &S){
    S.top = -1;    
}
int StackEmpty(SqStack &S){
    if(S.top == -1)
        return 1;
    else
        return 0;
}
void Push(SqStack &S,char x){
    if(S.top==MaxSize -1)
        return ;
    S.data[++S.top] = x;
}
void Pop(SqStack &S,char &x){
    if(S.top== -1)
        return;
    x = S.data[S.top--];
    
}
void GetTop(SqStack &S,char &x){
    if(S.top== -1)
        return ;
    x = S.data[S.top];
}
/*
    逆序 输出 
*/
void InverseStack(SqStack &S,SqStack &S1){
    char x;    
    while(S.top > -1){
        Pop(S,x);
        Push(S1,x);
    }
    while(!StackEmpty(S1)){
        Pop(S1,x);
        printf("%c",x);
    }

}

/*
    括号匹配  
*/
int Bracket_Match(char t[],int length){
    
    SqStack S;        
    InitStack(S);
    int i=0;
    while(i<length){
        char x ;
        if(t[i]==‘(‘ || t[i]==‘[‘ || t[i]==‘{‘){
            Push(S,t[i++]);
        }else {
            Pop(S,x);
            if(t[i] == ‘)‘ && x == ‘(‘){
                i++;
            }
            else if(t[i] == ‘]‘ && x ==‘[‘){
                i++;
            }
            else if(t[i] == ‘}‘ && x ==‘{‘){
                i++;    
            }else{
                return 0;
            }    
        }
    }
    
    return 1;
}
/*
    中缀转为后缀 
*/
int isNum(char x){
    if(x<=‘9‘ && x>=‘0‘){
        return 1;
    }else{
        return 0;
    }
}
int notPirio(char x,char exp){
    if((exp == ‘*‘ || exp == ‘/‘) && (x == ‘*‘ || x == ‘/‘)){
        return 1;
    }else if((exp == ‘+‘ || exp ==‘-‘) && (x == ‘+‘ || x==‘-‘)){
        return 1;
    }else if((exp == ‘+‘ || exp ==‘-‘) && (x == ‘*‘ || x == ‘/‘)){
        return 1;
    }else {
        return 0;
    }
}
void Postfix_exp(char exp[]){
    SqStack s1,s2;
    InitStack(s1);
    InitStack(s2);
    int i = 0;
    int count =0;
    char x;
    while(exp[i] != ‘\0‘){
        if(isNum(exp[i])){
            Push(s1,exp[i]);
            i++;
        }else if(exp[i] == ‘(‘){
            Push(s2,exp[i]);
            i++;
        }else if(exp[i] == ‘)‘){
            Pop(s2,x);
            while(x != ‘(‘){
                Push(s1,x);    
                Pop(s2,x);    
            }
            i++;
        }else{
            if(StackEmpty(s2)){
                Push(s2,exp[i++]);
            }
            else{
                GetTop(s2,x);
                while(notPirio(x,exp[i]) && !StackEmpty(s2)){
                    Pop(s2,x);
                    Push(s1,x);
                    GetTop(s2,x);
                }
                Push(s2,exp[i]);
                i++;
            } 
            
        }
    }
    while(!StackEmpty(s2)){
        Pop(s2,x);
        Push(s1,x);
    }
    InverseStack(s1,s2);
    
}
int main(){
    
    char tt[30]={
        ‘2‘,‘/‘,‘1‘,‘+‘,‘2‘,‘*‘,‘8‘,‘*‘,‘(‘,‘4‘,‘-‘,‘5‘,‘)‘,‘\0‘
    };
    char t[30]={
        ‘1‘,‘*‘,‘(‘,‘2‘,‘+‘,‘3‘,‘)‘,‘\0‘
    };
    Postfix_exp(tt);
    return 0;
}