P4831 简单表达式求值（基础）

解题思路

第一步，看懂运算优先级。 数学里规定"先乘除、后加减"，比如 3+42-6/3，要先算 42=8 和 6/3=2，再算 3+8-2，最后结果等于 9。我们写的程序也要遵守这个顺序，不能从左到右傻傻地直接算。

第二步，把表达式拆成数字和运算符。 用 cin.getline 读入整行表达式，然后从左到右扫描。每个数字可能是正数也可能是负数（前面带负号），还可能是小数（中间有小数点），要一个不漏地解析出来放进数组 val；运算符放进数组 op。比如 3+42 会得到 val=[3,4,2]，op=[+,]。

第三步，第一遍：先算乘除。 再开两个新数组 v2 和 o2。把第一个数字先放进 v2，然后逐个看运算符：遇到乘号 * 或除号 /，就直接拿它和 v2 里最后放的那个数字算出结果，再放回 v2；遇到加号 + 或减号 -，先把这个运算符存进 o2，把运算符后面的数字存进 v2。这样走完一遍，乘除全部算完，剩下的只有加减。

第四步，第二遍：再算加减。 现在 v2 里存着若干数字，o2 里存着加减号，正好是"数字、加减号、数字、加减号……"的样子，从左到右依次相加相减，就得到最终答案。例如 3+4*2-6/3：第一遍后 v2=[3,8,2]，o2=[+,-]，第二遍算 3+8-2=9，输出 9.00。

第五步，注意各种细节。 负数要能解析，比如 -3+4 表示负三加四，结果是 1；小数要能解析，比如 3.5 的整数部分和小数部分要拼在一起；最后结果用 printf("%.2f") 保留两位小数输出。题目保证表达式长度不超过16，数组开20格就足够装下。

参考代码

// 简单表达式求值：只含 + - * / 和数字（可负、可小数），先乘除后加减
#include <iostream>
#include <cstring>
using namespace std;

int main() {
    char s[20];
    double val[20] = {0};   // 解析出的数字
    char op[20];      // 解析出的运算符
    int nc = 0, oc = 0;
    // 读入整行表达式（可能含空格，逐个跳过）
    cin.getline(s, 20);
    int i = 0, len = (int)strlen(s);
    while (i < len) {
        if (s[i] == ' ') { i++; continue; }   // 跳过空格
        // 解析一个数字，可能有正负号和小数点
        int neg = 1;
        if (s[i] == '+' || s[i] == '-') {
            if (s[i] == '-') neg = -1;
            i++;
        }
        double x = 0;
        while (i < len && s[i] >= '0' && s[i] <= '9') {
            x = x * 10 + (s[i] - '0');
            i++;
        }
        if (i < len && s[i] == '.') {  // 小数点后的部分
            i++;
            double p = 0.1;
            while (i < len && s[i] >= '0' && s[i] <= '9') {
                x += (s[i] - '0') * p;
                p /= 10;
                i++;
            }
        }
        val[nc++] = neg * x;
        // 解析运算符
        if (i < len && s[i] != ' ') {
            op[oc++] = s[i];
            i++;
        }
    }
    // 第一遍：先处理乘除，结果压回数组
    double v2[20];
    char o2[20];
    int n2 = 0, o2c = 0;
    v2[n2++] = val[0];
    for (i = 0; i < oc; i++) {
        if (op[i] == '*' || op[i] == '/') {
            if (op[i] == '*') v2[n2 - 1] *= val[i + 1];
            else v2[n2 - 1] /= val[i + 1];
        } else {
            o2[o2c++] = op[i];
            v2[n2++] = val[i + 1];
        }
    }
    // 第二遍：从左到右处理加减
    double res = v2[0];
    for (i = 0; i < o2c; i++) {
        if (o2[i] == '+') res += v2[i + 1];
        else res -= v2[i + 1];
    }
    // 结果保留2位小数
    printf("%.2f\n", res);
    return 0;
}

复杂度分析

表达式的长度不超过16，扫描一遍解析数字和运算符只需要 O(16) 即常数时间；第一遍处理乘除、第二遍处理加减，每遍也只需要常数次操作。所以整个程序的时间复杂度是 O(1)，空间上几个数组大小都是常数，空间复杂度也是 O(1)。即使表达式中既有正负数又有小数，处理的步骤数也始终不超过表达式的长度。