#include<stdio.h>
#define MAXLEN 100
 
typedef struct           //定义一个结构体，充当运算符号栈
{  
    char data[MAXLEN];
    int top;                  
}OperatorStack;  
 
typedef struct          //再定义一个结构体，充当运算对象栈
{  
    float data[MAXLEN];
    int top;
}ObjectStack;
 
// 中缀表达式转后缀，需要用到运算符号栈
void trans(char infix[], char suffix[])         
{  
    OperatorStack opStack;
    char ch;            
    int i=0, j=0;
 
    // 初始化运算符号栈opStack
    opStack.top=-1;
 
    // 取中缀表达式的第一个字符
    ch=infix[i++];                    
 
    while(ch!='\0')               
    {
 
        switch(ch)
        {
        case '(':            // 遇到'('，则直接入栈
            opStack.top++;               
            opStack.data[opStack.top]=ch;        
            break;
 
        case ')':            // 遇到')'，一直出栈并输出，直到'('出栈
            while(opStack.data[opStack.top]!='(')   
            {
                suffix[j++]=opStack.data[opStack.top--];
            }
            opStack.top--;    // '('出栈，但不输出
            break;
 
        case '+':
        case '-':            // 遇到'+'或者'-'，则一直出栈，直到栈为空或者栈顶为'('
              while(opStack.top!=-1 && opStack.data[opStack.top]!='(')   
              {  
                    suffix[j++]=opStack.data[opStack.top--];  
              }
              opStack.top++;        // 然后ch再入栈
              opStack.data[opStack.top]=ch;
              break;
 
        case '*':
        case '/':
        case '%':// 遇到'*'或者'/'或者'%'，则一直出栈，直到栈顶不为'*'或'/'或'%'时
            while(opStack.data[opStack.top]=='/' || opStack.data[opStack.top]=='*'|| opStack.data[opStack.top]=='%')
            {
                suffix[j++]=opStack.data[opStack.top--];
            }
            opStack.top++;        // 然后ch再入栈
            opStack.data[opStack.top]=ch;
            break;
 
        case ' ':            // 遇到空格，则直接跳过，ch取中缀表达式中的下一个字符
            break;   
 
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
                case'10':    // 遇到数字，则直接输出到后缀表达式
            suffix[j++]=ch;
        }
        
        // 再读入infix[]中的一个字符到ch
        ch=infix[i++];            
    }
 
    while(opStack.top!=-1)            // 中缀表达式中所有字符处理完，当栈不为空时
    {
        suffix[j++]=opStack.data[opStack.top--];    // 将栈中剩余的运算符依次出栈到suffix[]中
    }
 
    suffix[j]='\0';                // 最后suffix[]以'\0'结束
}
 
/* 根据后缀表达式求值，需要用到运算对象栈 */
float compute(char suffix[])  
{  
    ObjectStack objStack;
    char ch;
    int j=0;
 
    // 初始化运算对象栈
    objStack.top=-1;
 
    // 取后缀表达式中的第一个字符
    ch=suffix[j++];
 
    // 开始求值
    while(ch!='\0')
    {
        if(ch=='+')            // 如果是加号，将2个数出栈，相加的结果再进栈
        {
            objStack.data[objStack.top-1]=objStack.data[objStack.top-1]+objStack.data[objStack.top];
            objStack.top--;
        }
        else if(ch=='-')   // 如果是减号，将2个数出栈，相减的结果再进栈
        {
            objStack.data[objStack.top-1]=objStack.data[objStack.top-1]-objStack.data[objStack.top];
            objStack.top--;
        }
        else if(ch=='*')   //如果是乘号，将2个数出栈，相乘的结果再进栈
        {
            objStack.data[objStack.top-1]=objStack.data[objStack.top-1]*objStack.data[objStack.top];
            objStack.top--;
        }
        else if(ch=='%')   //如果是取余号，将2个数出栈，相除的结果再进栈
        {
        
                objStack.data[objStack.top-1]=objStack.data[objStack.top-1]%objStack.data[objStack.top];
                objStack.top--;
            }
        else if(ch=='/')   //如果是除号，将2个数出栈，相除的结果再进栈
        {
            if(objStack.data[objStack.top]!=0)
            {   
                objStack.data[objStack.top-1]=objStack.data[objStack.top-1]/objStack.data[objStack.top];
                objStack.top--;
            }
        
            else
                printf("\n表达式中有除数为零，计算无效!\n ");
        }
        else if(ch>='0' && ch<='10')
        {
            objStack.top++;
            objStack.data[objStack.top]=(float)(ch-'0');  // 最后将算好的num压入栈
        }
 
        // 读后缀表达式中的下一个字符
        ch=suffix[j++];  
    }
 
    return objStack.data[objStack.top];  
}
 
void main()   
{   
    char infix[MAXLEN], suffix[MAXLEN];
 
    printf("\n请输入一个中缀表达式，其中只能含有+,-,*,/,%,(,)等运算符：");
    gets(infix);
   
    trans(infix, suffix);         
   
    printf("\n转换之后的后缀表达式为：%s\n", suffix);
    printf("\n后缀表达式求得的值为：%.3f\n\n", compute(suffix));
 
}