#include<iostream.h>
#define N 80
char stack[N];
int top=-1;
char infix[N];             /*儲存中序運算式*/
char postfix[N];           /*儲存後序運算式*/

 /*加入資料於堆疊內*/
 void push(int d)
 {
   if(top == N-1) {
      cout<<"堆疊滿了\n";
   }
   stack[++top]=d;
 }

 /*刪除堆疊的頂端資料*/
 char pop()
 {
   if(top == -1){
      cout<<"堆疊空了\n";
   }
   return(stack[top--]);
 }

 /*取得運算符的優先權*/
 int p(char d)
 {
   if(d=='*'||d=='/')               /*乘除運算符優先權最高*/
      return(2);
   else if(d=='+'||d=='-')          /*加減運算符優先權次之*/
      return(1);
   else                             /*否則必為'('，優先權最低*/
      return(0);
 }
 /*中序運算式轉為後序運算式*/
 void infix_to_postfix()
 {
   char token;
   int i=0, j=0;
   while((token=infix[i++])!='\0'){    /*讀取下一字元，並判斷是否為結束字元*/
      switch(token){
  case '(':push(token);
    break;
  case ')':while(stack[top]!='(')
       postfix[j++]=pop();
    pop();               /*將'('從堆疊內取出後丟棄不要*/
    break;
  case '+':
  case '-':
  case '*':
  case '/':/*不為空堆疊時，比較優先權*/
    while((top!= -1)&&(p(stack[top])>=p(token)))
       postfix[j++]=pop();
    push(token);
    break;
  default:postfix[j++]=token;   /*token為運算元時直接放入後序式*/
      } /* end of switch */
   } /* end of while */
   while(top != -1)
      postfix[j++]=pop();
 } /* end of infix_to_postfix */

 /*主程式*/
 void main()
 {
   cout<<"輸入中序四則運算式:";
   cin>>infix;
   infix_to_postfix();              /*呼叫函數將中序式轉為後序式*/
   cout<<"則後序四則運算式為:"<<postfix;
 }