#include<stdlib.h>
	#include<stdio.h>
	#define stack_init_size1 40
	#define stack_init_size2 20
	#define stackincrement1 40
	#define stackincrement2 20
	typedef struct{
	    int *base;
	    int *top;
	    int stacksize;
	}s_stack;
	typedef struct{
	    char *base;
	    char *top;
	    int stacksize;
	}f_stack;
	
	static char Weigh[8][9]=
	    {
	        {'>','>','<','<','<','>','>','<','>'},{'>','>','<','<','<','>','>','<','>'},
	        {'>','>','>','>','<','>','>','>','>'},{'>','>','>','>','<','>','>','>','>'},
	        {'<','<','<','<','<','=','>','<','>'},{'>','>','>','>','>','>','>','>','>'},
	        {'<','<','<','<','<','>','=','<','='},{'>','>','>','>','<','>','>','>','>'},
	        //{'<','<','<','<','<','>','=','<','='} 
	    };
	
	int Seriallize(char c)
	{
	    switch(c)
	    {
	    case '+': return 0;
	    case '-': return 1;
	    case '*': return 2;
	    case '/': return 3;
	    case '(': return 4;
	    case ')': return 5;
	    case '#': return 6;
	    case '^': return 7;
		case '\n': return 8;	
	    default:return 9;
	    }
	
	}
	
	void s_push(s_stack *s,int e)
	{
	
	     if(s->top-s->base>=s->stacksize)
	     {
	         s->base=(int *)realloc(s->base,(s->stacksize+stackincrement1)*sizeof(int));
	         if(!s->base) exit(0);
	         s->top=s->base+s->stacksize;
	         s->stacksize+=stackincrement1;
	     }
	    *s->top=e; s->top++;
	    /*printf("the s_stack has the data:%d\n",*(s->top-1));*/
	}
	void  f_push(f_stack *f,char e)
	{
	     if(f->top-f->base>=f->stacksize)
	     {
	         f->base=(char *)realloc(f->base,(f->stacksize+stackincrement2)*sizeof(char));
	         if(!f->base) exit (0);
	         f->top=f->base+f->stacksize;
	         f->stacksize+=stackincrement2;
	     }
	     *f->top=e;f->top++;
	    /* printf("the f_stack has the sign:%c\n",*(f->top-1));*/
	}
	
	int s_gettop(s_stack *s)
	{
	    s->top--;
	    return *s->top;
	}
	
	char f_gettop(f_stack *f)
	{
	    f->top--;
	    return *f->top;
	}
	bool f_ifempty(f_stack *f)
	{
		if (f->base==f->top)
		{
		  return true;
		}
		else
		{
		  return false;
		}
	}
	
	char EstimateCalculator(f_stack *f,char c)
	{
	    int m,n;
	    char w;
	    m=Seriallize(c);
	    w=*(f->top-1);
	    n=Seriallize(w);
	    return Weigh[n][m];
	}
	int Pow(int p,int q)
	{
		if (q==0)
		{
		   return 1;
		}
		else
		{
			return p*Pow(p,q-1);
		}
	}
	int Operate(int p,char r,int q)
	{
	        switch(r)
	    {
	        case '+': return q+p;
	        case '-': return p-q;
	        case '*': return q*p;
	        case '/': return p/q;
	        case '^': return Pow(p,q);
	    }
	}
	bool Calculate(int &Result)
	{
	    int h=0,iResult;
	
	    int iWrong=0;
		int iNumberOut=0;
	    char cNewChar;
	    s_stack istackNumber;
	    f_stack cstackCalculator;
	
	
	    istackNumber.base=(int*)malloc(stack_init_size1*sizeof(int));
	    if(!istackNumber.base) return 0;
	    istackNumber.top=istackNumber.base;
	    istackNumber.stacksize=stack_init_size1;
	
	    cstackCalculator.base=(char*)malloc(stack_init_size2*sizeof(char));
	    if(!cstackCalculator.base) return 0;
	    cstackCalculator.top=cstackCalculator.base;
	    cstackCalculator.stacksize=stack_init_size2;
	    *cstackCalculator.top='#';cstackCalculator.top++;
	
	    cNewChar=getchar();
		//getchar是一個一個字符讀入。
	    //比如12先讀入1，再讀入2。
		
		
		
		while((!(f_ifempty(&cstackCalculator))||(cNewChar!='\n'))&&(iWrong==0))
	    {//只要運算符號棧不空或者最后一次輸入的符號不是回車則運行以下程序. 
		 //換句話說,這段程序結(jié)束的條件是所有的運算符用完,
		 //而且當(dāng)前輸入的有時回車.	
			int t;
		    
	        int p,q;
	
	        char r;
	        if(Seriallize(cNewChar)==9)
			//當(dāng)前讀入的不是運算符，而是數(shù)。
	        {   
				if(h>0)//第h次讀入
				{
	               t=s_gettop(&istackNumber);
				   //取出數(shù)棧里最后一個數(shù)。
	               s_push(&istackNumber,t*10+cNewChar-48);
				   //把取出的數(shù)乘于10加上當(dāng)前讀入字符（減去48）對應(yīng)的數(shù)存回數(shù)棧。
				}
	   else s_push(&istackNumber,cNewChar-48);//第一個字符比如12的1。
	            h++;
				cNewChar=getchar();
	
	        }
	        else
			//當(dāng)前讀入的符號是運算符。
	        switch(EstimateCalculator(&cstackCalculator,cNewChar))
	        {
	          case '<'://當(dāng)前的運算符號的級別高于前一個運算符。
	               f_push(&cstackCalculator,cNewChar);
				   //運算符壓入
				   cNewChar=getchar();
				   h=0;
				   break;
	          case '='://當(dāng)前的運算符號的級別等于前一個運算符。
	               cstackCalculator.top--;
	               cstackCalculator.stacksize--;
				   //前一個運算符退棧。
	               if (cNewChar!='\n')
	               {
	                 cNewChar=getchar();
				   }
	               h=0;
				   break;
	          case '>'://當(dāng)前的運算符號的級別小于前一個運算符。
	               if (cstackCalculator.top-cstackCalculator.base<1)
	               {
	                 iWrong=1;
					 
				     }
				   else
				   {
					   r=f_gettop(&cstackCalculator);
					   //從運算符棧中取出當(dāng)前運算所需要的運算符.
				   }
				  
				   
	              
			      if ((istackNumber.top-istackNumber.base)>1)
				  {//從數(shù)棧里的數(shù)取出當(dāng)前要進(jìn)行運算的二個數(shù)進(jìn)行運算.
						   q=s_gettop(&istackNumber);
						   p=s_gettop(&istackNumber);
						   
						   iResult=Operate(p,r,q);
						   s_push(&istackNumber,iResult);
						   
				  }
				  else
				  {//數(shù)棧里的數(shù)不足兩個.
	
						   iWrong=1;
				  }
				  break;
				  
			}//switch
		}
	
		if(iWrong==1)
		{
			return false;
			Result=0;
	    }
		else
		{
			Result=s_gettop(&istackNumber);
			return true;
		}
		free(cstackCalculator);
		free(istackNumber);
	}
	
	
	
	int main()
	{
	    
		char cIfCalculate='y';
		
		while ((cIfCalculate=='y'))
		{
		   printf("please input the expression and end it with enter!\n");
		   int iResult;
	
		   bool blLegalExpression=Calculate(iResult);
		   if (blLegalExpression)
		   {
		      printf("the answer is %d\n",iResult);
		   }
		   else
		   {
			 printf("You have input the incorrect expression!!!\n");
		   }
		   printf("continue to calculate?press y to continue,and any key to break.");
		   cIfCalculate=getchar();
		   fflush(stdin);
		   //刷新標(biāo)準(zhǔn)輸入流,否則程序?qū)⒔又谀抢镒x入我們不需要的字符.
		}
		return 0;
	}