《程序设计与算法（二）算法基础》《第二周递归》四则运算表达式求值 4132...

阳光穿透心脏的1/2处 2023-08-17 16:23 60阅读 0赞

[https://www.cnblogs.com/xyqxyq/p/10211341.html][https_www.cnblogs.com_xyqxyq_p_10211341.html]

这一题我们可以通过递归求解，首先我们可以把一个表达式分为三部分，分别是：

（1）表达式 ：项、加减

（2）项：因子、乘除

（3）因子：数、（）表达式

这三项构成了递归的关系，我们可以看到，要求一个表达式的值，我们首先要求一个项的值，要求一个项的值，我们首先要求一个因子的值，要求一个因子的值，我们首先要看它是由什么组成的。

它既可以是由表达式加上括号组成的，也可以是由数组成，当发现它是数时，我们就计算这个数的大小。

浮点数的计算我们分为两部分，首先先算出整数部分的大小，不断地取一位然后看看是否结束，不结束就再取一位，将之前的乘十然后加上这一位，然后我们通过cin.peek()函数可以看到这一位是什么，如果这一位是 . 我们就开始小数部分的计算，和之前的类似，每次减小十倍而已。

如果是表达式的话，我们继续之前的那个过程，表达式 -> 项 -> 因子 ,不断地递归求解。

对于表达式的求值，我们首先求出第一项的值，看看是否有后一项，有的话我们就进行计算，没有就结束。因为当进行之后的递归的时候，我们是要吃掉后面的字符的，我们使用过之后就把它丢掉。

使用完+ - \* / ( ) 之后我们要把它吃掉，求项的时候我们也是相同的流程，先求一项，判断是否还有，然后进行下一步的操作，大致就是这样了。

/*
    递归
    四则运算表达式求值
    百练：4132
    输入没有空格
    */
    #include<iostream>
    #include<cstring>
    #include<cstdlib>
    #include<iomanip> // setprecision()
    
    using namespace std;
    double factor_value();
    double term_value();
    double expression_value();
    
    int main()
    {
        double ans = expression_value();
        cout << fixed<<setprecision(2)<<ans << endl;
        return 0;
    }
    
    double expression_value() // term add minus
    {
        // should have while loop, term add minus many times
        // (a+b+c+d)*b + c+ d 
        double result = term_value();
    
        bool more = true;
        while (more)
        {
            char c = cin.peek();
            if (c == '+' || c == '-')
            {
                char op = cin.get();
                double value = term_value();
                if (op == '+')
                    result += value;
                else
                    result -= value;
            }
            else
            {
                more = false;
            }
        }
        return result;
    }
    
    double term_value() // factor / *
    {
        double result = factor_value();
        while (true) // why here is  while loop ? eg: a*b*c*d + a*b*c
        {
            char op = cin.peek();
            if (op == '*' || op == '/')
            {
                cin.get();
                double value = factor_value();
                if (op == '*')
                    result *= value;
                else
                    result /= value;
            }
            else
                break;
    
        }
        return result;
    
    }
    
    double factor_value()
    {
        double result = 0;
        char c = cin.peek();
        if (c == '(')
        {
            cin.get();
            result = expression_value();
            cin.get();
        }
        else
        {
            while (isdigit(c))
            {
                result = result * 10 + c - '0';
                cin.get();
                c = cin.peek();
            }
            double tmp = 0;
            if (c == '.')
            {
                double base = 0.1;
                
                cin.get();
                char ch = cin.peek();
                while (isdigit(ch))
                {
                    tmp = (ch-'0')*base + tmp;
                    base = 0.1*base;
                    cin.get();
                    ch = cin.peek();
                }
    
            }
            result += tmp ;
        }
        return result;
    }

转载于:https://www.cnblogs.com/focus-z/p/11443202.html

[https_www.cnblogs.com_xyqxyq_p_10211341.html]: https://www.cnblogs.com/xyqxyq/p/10211341.html