#define STACK_INIT_SIZE  100
#define STACKINCREMENT   10
#include"stdio.h"
#include"stdlib.h"

typedef struct SqStack                //栈的顺序存储结构
{
  double *base;
  double *top;
  int stacksize;
}SqStack;

void InitStack (SqStack &S)           //构造一个空栈
{
  S.base=(double *)malloc(STACK_INIT_SIZE*sizeof(double));              //分配储存空间
  if(!S.base) exit (-1);                                                      //空间分配失败
  S.top=S.base;
  S.stacksize=STACK_INIT_SIZE;                                                //空间初始分配
}//InitStack

bool GetTop (SqStack S,double  &e)
{                         //若栈不空，则用e返回S的栈顶元素，并返回true；否则返回false
  if(S.top==S.base)
   return false;
  e=*(S.top-1);
  return true;
}//GetTop

bool Push(SqStack &S,double e)
{                        //插入元素为e的新的栈顶元素
  if(S.top-S.base>=S.stacksize)
  {                       //栈满，追加存储空间
    S.base=(double*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(double));
     if(!S.base)  
   exit(-1);            //存储空间分配失败
     S.top=S.base+S.stacksize;                       //此处内存有可能重新分配,S.base地址有可能会变，此句不能省
     S.stacksize+=STACKINCREMENT;
  }
  *S.top++=e;               //top自增
  return true;
}// Push

bool  Pop(SqStack &S,double &e)                  //若栈不空，则删除S的栈顶元素，用e返回其值
{
  if(S.top==S.base)
   return false;
  e=*--S.top;                      //删除一个元素,top减一
  return true ;
}// Pop

char Precede(char a1 ,char a2)//判定运算符的优先级。
{       
  char r;
  switch(a2)
  {
    case'+':      //此处由于加减几乎优先级一样，故放在一起
    case'-':
     if(a1=='('||a1=='#')
   r='<';
     else
   r='>';
     break;
    case'*':      //此处由于乘除优先级一样，故放在一起
    case'/':
     if(a1=='*'||a1=='/'||a1==')')
   r='>';
     else
   r='<';
     break;
    case'(':
     if(a1==')')
     {
    printf("括号匹配错误!\n");
    exit(-1);
     }
     else
   r='<';
     break;
    case')':
     if(a1=='(')
   r='=';
     else if(a1=='#')
     {
    printf("eeror!没有左括号\n");
    exit (-1);
     }
     else
   r='>';
     break;
    case'#':
     switch(a1)
     {
      case'#':
    r='=';
     break;
      case'(':
    printf("eeror!没有右括号\n");
    exit(-1);
      default:
    r='>';
     }//switch
     break;
  }//switch
  return r;
}//Precede

bool In(char d)                   //判断c是否为七种运算符之一
{
  switch(d)
  {
   case'+':
   case'-':
   case'*':
   case'/':
   case'(':
   case')':
   case'#':
    return true;
   default:
    return false;
  }//switch
}
 

double Operate( double a,  double theta, double b )       //Operate为进行二元运算的a theta b的函数
{
  char n=char(theta);             //此处把double型强制转换成int型，虽然会造成精度缺失，但本身theta是一个符号，也算是整型
  switch(n)                       //转换后相当于和符号匹配ACSII码
  {
   case'+':
    return a+b;
   case'-':
    return a-b;
   case'*':
    return a*b;
     default:
    if(b!=0)
     return a/b;
    else
    {
    printf("error!除数不能为零\n");
    exit(-1);
    } 
  }//switch
}
 

double EvaluateExpression()
{       //算符表达式的优先算法。设OPTR和OPND分别为运算符栈和运算数栈
  SqStack OPTR,OPND;
  char  c;
  char Data[11];                     //定义此数组为了存放整数或小数
  double a,b,d,e;
  InitStack(OPTR);                   //构造一个运算符栈
  InitStack(OPND);                   //构造一个运算数栈
  Push(OPTR,'#');                    //将#压入栈底
  c=getchar();
  GetTop(OPTR,e);
  while(c!='#'||e!='#')              //栈顶不是#号且输入不是#号
  {
    if(In(c))//是符号则进栈
    {
      switch(Precede(e,c))
      {
       case'<':   //栈顶元素优先级低
     Push(OPTR,c);
     c=getchar();
     break;
       case'=':    //脱括号并接受下一字符
     Pop(OPTR,e);
     c=getchar();
     break;
       case'>':    //退栈并将运算结果入栈
     Pop(OPTR,e);
     Pop(OPND,b);
     Pop(OPND,a);
     Push(OPND,Operate(a,e,b));
     break;
      }//switch
    }
       else if(c>='0'&&c<='9'||c=='.')
    {
    int i=0;
    while(c>='0'&&c<='9'||c=='.')
    {
     Data[i]=c;
     i++;
     c=getchar();
    }
    Data[i]='\0';                      //数字没有存满,输入字符串结束符
    d=atof(Data);                      //此处是把数组里的数字，实际上是按字符串；转换为double类型，然后把浮点型数字入栈
    Push(OPND,d);                      //atof函数的形参是指针类型，故用数组名
    }
    else
    {
     printf("error!输入错误!\n");
     exit(-1);
    }
       GetTop(OPTR,e);
  }//while
  GetTop(OPND,e);
  return e;
}//EvaluateExpression
 

main()
{
  char ch;
  double  result;
  printf("请输入表达式，以#号结束\n");
  result=EvaluateExpression();
  printf("结果为%f:\n",result);
  printf("您想再试一次吗？如果想，请输入'Y';否则输入'N'\n");
  fflush (stdin);
  ch=getchar();
  while(ch=='Y'||ch=='y'){
   printf("请输入表达式，以#号结束\n");
   fflush (stdin);
   result=EvaluateExpression();
   printf("结果为%f:\n",result);
   fflush (stdin);
  }
}