BJFU数据结构 基于栈的中缀算术表达式求值

BJFU数据结构 基于栈的中缀算术表达式求值

描述

输入一个中缀算术表达式，求解表达式的值。运算符包括+、-、*、/、(、)、=，参加运算的数为double类型且为正数。（要求：直接针对中缀算术表达式进行计算，不能转换为后缀或前缀表达式再进行计算，只考虑二元运算即可。）

输入

多组数据，每组数据一行，对应一个算术表达式，每个表达式均以“=”结尾。当表达式只有一个“=”时，输入结束。参加运算的数为double类型。

输出

对于每组数据输出一行，为表达式的运算结果。输出保留两位小数。

输入样例 1 

2+2=
20*(4.5-3)=
=

输出样例 1

4.00
30.00

思路: AcWing 3302. 表达式求值：多图讲解运算符优先级+详细代码注释 - AcWing

C语言atof函数介绍: C 库函数 – atof() | 菜鸟教程

#include
#include
#include
#include 
#include 

using namespace std;
int pre(char c)//优先级判断
{

    if(c=='=') return 0;
    else if(c=='+'||c=='-')
        return 1;
    else if(c=='*'||c=='/')
        return 2;
    else return 0;
}
void calculate(stack &num,stack &op)//运算
{

    double b=num.top();
    num.pop();
    double a=num.top();
    num.pop();
    switch(op.top())
    {

        case '+':num.push(a+b);
            break;
        case '-':num.push(a-b);
            break;
        case '*':num.push(a*b);
            break;
        case '/':num.push(a/b);
            break;
    }
    op.pop();
}
int main()
{

    stack num;//存储数字
    stack op;//存储 *** 作符
    char s[100];
    while(1)//可多次输入式子
    {

        scanf("%s",s);//读取整个字符串
        if(!strcmp(s,"="))//唯一的循环出口
            break;
        for(int i=0;s[i]!='';i++)
        {

            if(isdigit(s[i]))//判断是否为数字
            {

                double temp=atof(s + i);//转化为浮点数
                num.push(temp);//入栈
                while(isdigit(s[i])||s[i]=='.')//寻找下一个字符
                    i++;
                i--;//由于有外层循环，往前挪一位
            }
            else//字符是 *** 作符
            {

                if(s[i]=='(')
                    op.push(s[i]);
                else if(s[i]==')')
                {

                    while(op.top()!='(')//计算括号内的式子
                        calculate(num,op);
                    op.pop();//左括号出栈
                }
                else if(op.empty()||pre(s[i])>pre(op.top()))//优先级大于栈顶，或栈为空时，直接进栈
                    op.push(s[i]);
                else if(!op.empty()&&pre(s[i])<=pre(op.top()))//是优先级不大于栈顶的操作符，且栈不空，先进行运算操作
                {

                    while(!op.empty()&&pre(s[i])<=pre(op.top()))
                        calculate(num,op);
                    op.push(s[i]);//将优先级大于它的操作做完再让它进栈
                }
            }
        }
        printf("%.2lfn",num.top());//输出结果
        num.pop();
        op.pop();//清空栈
    }
    return 0;
}