#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef int ElemType;

#define STACK_INIT_SIZE 100

typedef struct    //順序棧類型定義
{
	ElemType *base;
	ElemType *top;
   	int  stacksize; //棧頂指針
}SeqStack;

void InitStack(SeqStack &S)
{
	S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
	if(!S.base)printf("overflow!\n");
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
}


void Push(SeqStack &S,ElemType e)
{
	if(S.top-S.base>=S.stacksize)
      printf("overflow!\n");
     *S.top++=e;	
}

ElemType Getop(SeqStack &S)
{
	ElemType e;
	if(S.top==S.base)	printf("error!\n");
     e=*(S.top-1);
    return e;
}


ElemType Pop(SeqStack &S)
{
	ElemType e;
	if(S.top==S.base)  printf("error!\n");
	e=*--S.top;
    return e;
}

int Precedence(char op);
void Change(char* s1, char* s2);
int Compute(char* str);

void main()
{ 
  	char s1[100];
	char s2[100];
    int x;
	printf("輸入以@結尾的中綴表達式:\n\n");

	gets(s1);
	printf("\n\n");
	printf("中綴表達式為：");
	puts(s1);printf("\n");
	Change(s1,s2);
    printf("后綴表達式為：");
	puts(s2);printf("\n");
	x=Compute(s2);
    printf("計算結果為：%d\n",x);
    printf("\n\n\n\n");


}
void Change(char* s1, char* s2)
       
{
            
	SeqStack S;
	InitStack(S);  
	Push(S,'@');      
	int i,j;
	i=0;             
	j=0;              
	char ch=s1[i];    
	while(ch!='@') 
	{                
	     
		if(ch=='(') 
		{           
		     Push(S,ch);
		     ch=s1[++i];
		}
		else if(ch==')') 
		{          
		    while(Getop(S)!='(') 
                s2[j++]=Pop(S);
			Pop(S);  
			ch=s1[++i];
		}
		else if(ch=='+'||ch=='-'||ch=='*'||ch=='/') 
		{           
		    char w=Getop(S);
		    while(Precedence(w)>=Precedence(ch)) 
            {       
		        s2[j++]=w; 
			    Pop(S); w=Getop(S);
			}
			Push(S,ch);  
			ch=s1[++i];
		}
        else 
        {        
		  	    s2[j++]=ch;  
			    ch=s1[++i];
		}
	}
 
	ch=Pop(S);
	while(ch!='@') {
	    if(ch=='(') 
		{
	        printf("expression error!\n");
	        exit(1);
		}
	    else 
		{
		    s2[j++]=ch; 
		    ch=Pop(S);
		}
	}
 
	s2[j++]='@'; 
	s2[j++]='\0';
}


  int Precedence(char op)
        
  {
      switch(op) 
	  {
	      case '+':
          case '-':
	          return 1;  
          case '*':
	      case '/':
	          return 2;  
	 	  case '(':
          case '@':
		  default: 
		      return 0;  
	  }
  }

int Compute(char* str)
      
{
  
    SeqStack S;
	InitStack(S);    
          
    int i=0;
	char ch=str[i];
	int x=0;
	while(ch!='@')
	{                   
	   if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
	   {	switch(ch)
	     {
	         case '+':
	             x=Pop(S)+Pop(S); 
			     break;
		     case '-':
			     x=Pop(S);  
			     x=Pop(S)-x; 
			     break;
		     case '*':
			     x=Pop(S)*Pop(S);
			     break;
		     case '/':
			     x=Pop(S);       
			     if(x!=0.0)
			         x=Pop(S)/x;  
			     else { 
			         printf("Divide by 0!   ERROR!\n\n\n\n");
			         exit(1);
			     }
			     break;
		   
		 }
		 Push(S,x);
	   }
		 
	   else 
		   Push(S,ch-48);
	  ch=str[++i];
	}
	if(S.top!=S.base) 
	{  
	     x=Pop(S);
	     if(S.top==S.base) return x;  
		 else {
		     printf("expression error!\n");
		     exit(1);
		 }
	}
	else { 
	    printf("expression error!\n");
	    exit(1);
	}
}