P4816 波兰表达式（基础）

解题思路

1. 认识波兰表达式。 普通写法是"2 + 3"（运算符在中间），波兰表达式把运算符写在最前面，比如 "+ 2 3" 就表示 2+3，"(2+3)4" 写成 " + 2 3 4"。因为运算符在前，读到一个运算符时，它后面必然跟着两个操作数（可能是数字，也可能是更长的表达式）。
2. 用递归求值最方便。 写一个函数 parse()：先读入一个 token（用空格隔开）。如果它是运算符 + - * /，就递归地调用两次 parse() 得到左、右两个操作数的值，再按运算符算出结果；如果它是一个数字，就直接转成浮点数返回。
3. 把表达式想成一棵树。 运算符是根，左右操作数是两棵子树，递归求值就是"先求左子树、再求右子树、最后回到根计算"，和普通表达式的计算顺序完全一致。
4. 小心负数！ 判题数据里可能出现负数，比如 -27025.824891，负号和数字之间没有空格。这时 token 的第一个字符虽然也是 '-'，但它不是运算符，而是数字的一部分。判断方法：只有当 token 是单个字符且是 + - * / 时才当运算符，否则都用 atof 转成数字。
5. 输出格式。 题目要求用 printf("%f\n", 值) 输出，也就是固定保留 6 位小数。

参考代码

// 波兰表达式：运算符前置的前缀表达式，用递归解析每个运算符和它左右两个操作数来求值
// 注意：判题数据里可能出现负数（如 -27025.824891），负号的后面紧跟着数字，要与单个"-"运算符区分开
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

// 递归读入并求一个操作数或一个运算符及其左右操作数的值
double parse() {
    char token[30];
    cin >> token;
    // 只有单独一个字符（后面没有数字）的 + - * / 才是运算符
    if (token[1] == '\0' &&
        (token[0] == '+' || token[0] == '-' || token[0] == '*' || token[0] == '/')) {
        double left = parse();   // 递归求左边操作数的值
        double right = parse();  // 递归求右边操作数的值
        if (token[0] == '+') return left + right;
        if (token[0] == '-') return left - right;
        if (token[0] == '*') return left * right;
        return left / right;
    }
    return atof(token);   // 是数字（可能是负数），直接转成浮点数
}

int main() {
    double value = parse();
    printf("%f\n", value);   // 按题目要求格式输出
    return 0;
}

复杂度分析

每个 token 只会被读取和处理一次，所以时间复杂度是 O(T)，T 是表达式里 token 的总个数。递归层数等于表达式嵌套的深度，本题数据规模下完全安全，不会爆栈。空间主要是递归调用栈，深度有限，占用很少。