#include<stdio.h>
#include<stdlib.h>
#include <conio.h>
#include<math.h>
#include<string.h>
#define N 25  //最大表达式长度
#define OP 1   //OP为运算符,值为1
#define NUM 0   //NUM为数字，值为0
#define MAXSIZE 100
typedef char datatype;
typedef struct{
  datatype a[MAXSIZE];
  int top;
  }sequence_stack;
void init(sequence_stack *st)//栈初始化
{
    st->top=0;
}
int empty(sequence_stack st)//判断栈是否为空
{
    return(st.top?0:1);
}
datatype read(sequence_stack st)//读栈顶结点值
{
    if(empty(st))
    {
        printf("\n栈是空的！");exit(1);
    }
   else return st.a[st.top-1];
}
void push(sequence_stack *st,datatype x)//进栈
{
    if(st->top==MAXSIZE)
    {
        printf("\nThe sequence stack is full!");exit(1);
    }
    st->a[st->top]=x;
    st->top++;
}
void pop(sequence_stack *st)//出栈
{
    if(st->top==0)
    {
        printf("\nThe sequence stack is empty!");exit(1);
        st->top--;
    }
}
int match_kuohao(char c[])//判断表达式括号是否匹配
{
    int i=0;
    sequence_stack s;
    init(&s);
    while(c[i]!='#')
    {
        switch(c[i])
        {
            case'{':
            case'[':
            case'(':push(&s,c[i]);break;
            case'}':if(!empty(s)&&read(s)=='{')
                     {
                         pop(&s);break;
                     }
                     else return 0;
            case']':if(!empty(s)&&read(s)=='[')
                     {
                         pop(&s);break;
                     }
                     else return 0;
            case')':if(!empty(s)&&read(s)=='(')
                     {
                         pop(&s);break;
                     }
                     else return 0;
        }
        i++;
    }
    return(empty(s));
}
double readnumber(char f[],int *i)//将数字字符串转变成相应的数
{
    double x=0.0;
    int k=0;
    while(f[*i]>='0'&&f[*i]<='9')
    {
        x=x*10+(f[*i]-'0');
        (*i)++;
    }
    if(f[*i]=='.')
    {
        (*i)++;
        while(f[*i]>='0'&&f[*i]<='9')
        {
           x=x*10+(f[*i]-'0');
           (*i)++;k++;
        }
    }
    while (k!=0)
    {
        x=x/10.0;
        k=k-1;
    }
    return(x);
}
double qiuzhi(char f[])//求一个后缀表达式的值
{
    double obst[100];
    int top=0;
    int i=0;
    double x1,x2;
    while(f[i]!='#')
    {
         if (f[i]>='0'&&f[i]<='9')
         {
            obst[top]=readnumber(f,&i);top++;
         }
         else if(f[i]==' ') i++;
         else if(f[i]=='+')
         {
             x2=obst[--top];
             x1=obst[--top];
             obst[top]=x1+x2;top++;
             i++;
         }
         else if (f[i]=='-')
         {
             x2=obst[--top];
             x1=obst[--top];
             obst[top]=x1-x2;top++;
             i++;
         }
         else if (f[i]=='*')
         {
             x2=obst[--top];
             x1=obst[--top];
             obst[top]=x1*x2;top++;
             i++;
         }
         else if (f[i]=='/')
         {
             x2=obst[--top];
             x1=obst[--top];
             obst[top]=x1/x2;top++;
             i++;
         }
    }
    return obst[0];
}
int is_op(char op)//判断一个字符是否为操作符
{
    switch(op)
    {
        case '+':
        case '-':
        case '*':
        case '/':return 1;
        default:return 0;
    }
}
int youxianji(char op)//求运算符的优先级
{
    switch(op)
    {
       case '#':return -1;
       case '(':return 0;
       case '+':
       case '-':return 1;
       case '*':
       case '/':return 2;
       default:return -1;
    }
}
void z_h(char e[],char f[])//将一个中缀表达式e转换为它等价的后缀表达式
{ int i=0;
    int j=0;
    char opst[100];
    int top,t;
    top=0;
    opst[100]='#';top++;
    while(e[i]!='#')
    {
        if((e[i]>='0'&&e[i]<='9')||e[i]=='.')
        f[j++]=e[i];
        else if(e[i]=='(')
          {
              opst[top]=e[i];top++;
          }
          else if(e[i]==')')
          {
              t=top-1;
              while (opst[t]!='(')
                     {
                         f[j++]=opst[--top];t=top-1;
                     }
                     top--;
          }
          else if(is_op(e[i]))
          {
              f[j++]=' ';
              while (youxianji(opst[top-1])>=youxianji(e[i]))
              f[j++]=opst[--top];
              opst[top]=e[i];top++;
          }
          i++;
    }
    while (top) f[j++]=opst[--top];
}
void main()
{
    system("cls");
	system("color 9F");
    sequence_stack s;
	init(&s);
    char f[100];
	char e[100];
    datatype ch;
    double x;
    int k=0;int i;int j;
    printf("请输入表达式:");
    for(i=0;(ch=getchar())!='\n'&&k<=N;i++)
    {
        e[i]=ch;
        push(&s,ch); 
        k++;
    }
    e[i+1]='#';
	printf("显示表达式:");
	for(i=0;e[i]!='#';i++)
	{printf("%f",e[i]);}
    z_h(e,f);
   readnumber(f,&j);
  x=qiuzhi(f);
  printf("表达式的结果为：",x);
}