#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include"math.h"
#define true 1
#define false 0
#define OPSETSIZE 8
typedef int Status;
unsigned char Prior[8][8] =
{ // 運算符優(yōu)先級表
 // '+' '-' '*' '/' '(' ')' '#' '^'
 /*'+'*/'>','>','<','<','<','>','>','<',
 /*'-'*/'>','>','<','<','<','>','>','<',
 /*'*'*/'>','>','>','>','<','>','>','<',
 /*'/'*/'>','>','>','>','<','>','>','<',
 /*'('*/'<','<','<','<','<','=',' ','<',
 /*')'*/'>','>','>','>',' ','>','>','>',
 /*'#'*/'<','<','<','<','<',' ','=','<',
 /*'^'*/'>','>','>','>','<','>','>','>'
};
typedef struct StackChar
{
 char c;
 struct StackChar *next;
}SC;       //StackChar類型的結點SC
typedef struct StackFloat
{
 float f;
 struct StackFloat *next;
}SF;       //StackFloat類型的結點SF
SC *Push(SC *s,char c)          //SC類型的指針Push，返回p
{
 SC *p=(SC*)malloc(sizeof(SC));
 p->c=c;
 p->next=s;
 return p;
}
SF *Push(SF *s,float f)        //SF類型的指針Push，返回p
{
 SF *p=(SF*)malloc(sizeof(SF));
 p->f=f;
 p->next=s;
 return p;
}
SC *Pop(SC *s)    //SC類型的指針Pop
{
 SC *q=s;
 s=s->next;
 free(q);
 return s;
}
SF *Pop(SF *s)      //SF類型的指針Pop
{
 SF *q=s;
 s=s->next;
 free(q);
 return s;
}
float Operate(float a,unsigned char theta, float b)      //計算函數Operate
{
 switch(theta)
 {
 case '+': return a+b;
 case '-': return a-b;
 case '*': return a*b;
 case '/': return a/b;
 case '^': return pow(a,b);
 default : return 0;
 }
}
char OPSET[OPSETSIZE]={'+','-','*','/','(',')','#','^'};
Status In(char Test,char *TestOp)
{
 int Find=false;
 for (int i=0; i< OPSETSIZE; i++)
 {
  if(Test == TestOp[i])
   Find= true;
 }
 return Find;
}
Status ReturnOpOrd(char op,char *TestOp)
{
 for(int i=0; i< OPSETSIZE; i++)
 {
  if (op == TestOp[i])
   return i;
 }
}
char precede(char Aop, char Bop)
{
 return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];
}
float EvaluateExpression(char* MyExpression)
{
 // 算術表達式求值的算符優(yōu)先算法
 // 設OPTR和OPND分別為運算符棧和運算數棧，OP為運算符集合
 SC *OPTR=NULL;       // 運算符棧，字符元素
 SF *OPND=NULL;       // 運算數棧，實數元素
 char TempData[20];
 float Data,a,b;
 char theta,*c,Dr[]={'#','\0'};
 OPTR=Push(OPTR,'#');
 c=strcat(MyExpression,Dr);
 strcpy(TempData,"\0");//字符串拷貝函數
 while (*c!= '#' || OPTR->c!='#')
 {
  if (!In(*c, OPSET))
  {
   Dr[0]=*c;
   strcat(TempData,Dr);           //字符串連接函數
   c++;
   if (In(*c, OPSET))
   {
    Data=atof(TempData);       //字符串轉換函數(double)
    OPND=Push(OPND, Data);
    strcpy(TempData,"\0");
   }
  }
  else    // 不是運算符則進棧
  {
   switch (precede(OPTR->c, *c))
   {
   case '<': // 棧頂元素優(yōu)先級低
    OPTR=Push(OPTR, *c);
    c++;
    break;
   case '=': // 脫括號并接收下一字符
    OPTR=Pop(OPTR);
    c++;
    break;
   case '>': // 退棧并將運算結果入棧
    theta=OPTR->c;OPTR=Pop(OPTR);
    b=OPND->f;OPND=Pop(OPND);
    a=OPND->f;OPND=Pop(OPND);
    OPND=Push(OPND, Operate(a, theta, b));
    break;
   } //switch
  }
 } //while
 return OPND->f;
} //EvaluateExpression
int main(void)
{
 char s[128];
 puts("請輸入表達式:");
 gets(s);
 puts("該表達式的值為:");
 printf("%s\b=%g\n",s,EvaluateExpression(s));
 system("pause");
 return 0;
}