#include<iostream>
#include<cstdlib>
#define STACK_INIT_SIZE 10;
//#define STACKINCREMENT 10;
using namespace std;
 
typedef struct { //構造棧 
       char* top;
       char* base;
       int  stacksize;
       }Stack; 
       
int JudegPri(char c,Stack s,char a[7],char b[7][7]); //優先級判斷函數 
bool JudgeOperate(char c,char a[7]);  //運算符判斷函數  

bool InitStack(Stack &s) //棧的初始化 
 {
  s.base=(char*)malloc(15*sizeof(char));//初始空間分配 
  if(!s.base) return 0;
  s.top=s.base;
  s.stacksize=STACK_INIT_SIZE;//棧大小初始化 
  return 1;          
 }
 
char push(Stack &s,char e)//壓棧 
{   
  *s.top++=e;  
} 

char pop(Stack &s,char e)//出棧 
{
   e=*--s.top;
}

char GetTop(Stack s,char e)//獲取棧頂元素 
{
 if(s.top==s.base)  return 0;  
 e=*(s.top-1);
 return e;
}  

int main()  //主函數 
{
  Stack s;// 構造棧Stack的對象 s
  InitStack(s);//調用棧初始化函數 
  bool flag=1; //棧為空的標志,1表示非空    
  bool sign=1;
  int  label =0;
  char c;//當前元素 
  char e;//棧頂元素 
  char a[7]={'+','-','*','/','#','(',')'};//用#替代↑ 
  char b[7][7]={ {'=','=','<','<','<','>','>'},  //運算符優先級關系矩陣 
                  {'=','=','<','<','<','<','>'},
                  {'>','>','=','=','<','<','>'},
                  {'>','>','=','=','<','<','>'},
                  {'>','>','>','>','=','<','>'},
                  {'<','<','<','<','<','=','='},
                  {'<','<','<','<','<',' ','='}
                };
loop:
 cout<<"請輸入中綴運算表達式,以$結尾"<<endl;
  while(flag)
 { sign=1;
   cin>>c;  //輸入一個字符 
   if(c=='$') //字符等于$時，表示輸入串為空 
   { while(s.top!=s.base) //棧不空 
        {  
             cout<<pop(s,e)<<" ";  //退棧輸出 
        }
     flag=0; //棧為空的標志   
   } //  if(c==' ') 
   
   else if(!JudgeOperate(c,a))//(c!=' ')//如果是運算符 
      { if(c=='(')
           { label++;
             push(s,c);
           }
       else if(s.top!=s.base)  //棧不空 
        {
          if(JudegPri(c,s,a,b))//是運算符 、棧也不空，判斷輸入符號優先級高于當前棧頂符號優先級 
              push(s,c);
          else  //判斷輸入符號優先級是否高于當前棧頂符號優先級 
             if(c==')') //輸入符號是')' 
             { label--;
               while(sign)
               { 
                 if(GetTop(s,e)=='(')   //棧頂符號是'('
                      {
                        pop(s,e);  //退棧
                        sign=0; //
                      }
                 else 
                   { if(s.top==s.base) //棧空  
                       {    
                        cout<<"error!";
                        sign=0;
                        flag==0;
                       } 
                      else  cout<<pop(s,e)<<" ";//退棧輸出 
                   } 
               }//while(sign)
             }// if(c==')') 輸入符號是“)”    
           
          else {
                cout<<pop(s,e);//退棧輸出 ,應該繼續判斷棧是否為空
                //及優先級，如果不空，優先級不高就出棧 ，否則進棧 
                while(s.top!=s.base&&(!JudegPri(c,s,a,b)))
                    cout<<pop(s,e)<<" ";
                push(s,c);
               }                                 
        } //  if(s.top!=s.base)  //棧不空  
       
    else  push(s,c);    //棧空 ,運算符進棧                            
   } //if(JudgeOperate(c,a))

   else cout<<c<<" ";//如果不是運算符，直接輸出 
  }
  cout<<endl;
  if(label!=0)  {cout<<"Input Error ! Try Again! "<<endl;
                  label=0;
                  flag=1;
                  goto loop;
                  
                }
  system("pause");
}


int JudegPri(char c,Stack s,char a[7],char b[7][7])//判斷優先級，若當前優先級高返回1 ，否則返回0 
{   
    char e;
    int k,d;
    for(int i=0;i<7;i++)
      {
      if(a[i]==c)   //當前運算符 
         k=i;
      if(a[i]==GetTop(s,e)) //棧頂運算符 
        d=i;  
       }
    if(b[k][d]=='>')//若當前運算符優先級高，返回1 
         return 1;   
      else return 0;//否則，返回0 
}

 bool JudgeOperate(char c,char a[7])//判斷是不是運算符 ，是返回0，否則返回1
{ bool signal=1;
  for(int j=0;j<7;j++)  
    if(c==a[j])    //是運算符時，標記 signal=0
        signal=0;  
    return signal;  //否則，標記 signal=1         
 }