P4820 前缀式计算（提高）

解题思路

这道题要我们算一个“前缀表达式”的值。我们平时写的 $2+(3+4)\times5$ 叫中缀表达式，运算符在两个数的中间；前缀表达式把运算符写在两个数的前面，比如 $+ 2 * + 3 4 5$，它的值就是 $37$。

第一步，想清楚怎么从右往左算。 前缀表达式有个特别的地方：从右往左看，先遇到的一大串是数字；遇到运算符时，它正好管住它左边刚出现的两个数。所以我们用一个栈，从最后一个数开始从右往左扫：

1. 扫到一个数字，就把它压进栈里；
2. 扫到一个运算符，就从栈顶弹出两个数：先弹出的是左边的数，后弹出的是右边的数，算出结果再压回栈里。

第二步，注意弹出的顺序。 栈是“后进先出”的。以 $+ 2 * + 3 4 5$ 为例，从右往左先压入 5、4、3，栈顶是 3，遇到 + 时先弹出 3 再弹出 4，算 3 + 4 = 7 压回；接着遇到 *，弹出 7 和 5，算 7 × 5 = 35；再压入 2，遇到最前面的 +，弹出 2 和 35，算 2 + 35 = 37。加法和乘法先后顺序没关系，但减法和除法一定要分清：先弹出的是左边的数，后弹出的是右边的数，$a-b$ 不能写成 $b-a$，$a/b$ 也不能写成 $b/a$，顺序搞反就错了。

第三步，注意小数和保留两位小数。 题目说操作数可能是小数，比如 $2.5$，所以栈要用 double 存。读进来的是字符串，要自己把“整数部分 + 小数点 + 小数部分”拼成一个实数。最后输出用 fixed 固定小数位数、保留 2 位小数，比如 37 要输出成 37.00。

第四步，边界情况。 操作数最多 500 个，整个表达式最多 1000 个部分，栈开 2000 足够。计算过程中不会出现绝对值超过 $10^8$ 的数，不会溢出。

小结： 前缀表达式就是“倒过来看的后缀表达式”，从右往左用栈：遇到数字入栈，遇到运算符弹两个算一个，最后栈里剩下的就是答案。

参考代码

// 用途：计算前缀表达式（波兰式）的值，操作数可能是小数，结果保留两位小数
#include <iostream>
using namespace std;

// 数值栈，保存运算中的中间结果
double st[2000];
int top = 0;

// 把字符串形式的数字（可能是小数）转换成 double
double toDouble(const char* s) {
    double val = 0.0;
    int i = 0;
    // 先读整数部分
    while (s[i] >= '0' && s[i] <= '9') {
        val = val * 10 + (s[i] - '0');
        i++;
    }
    // 再读小数点后的小数部分
    if (s[i] == '.') {
        i++;
        double scale = 0.1;  // 当前小数位代表的数
        while (s[i] >= '0' && s[i] <= '9') {
            val = val + (s[i] - '0') * scale;
            scale = scale * 0.1;
            i++;
        }
    }
    return val;
}

int main() {
    char tok[2000][20];  // 保存整个前缀表达式的每个部分
    int cnt = 0;
    while (cin >> tok[cnt]) {
        cnt++;
    }
    // 前缀表达式要从右往左扫描：遇到数字入栈，遇到运算符取栈顶两个数计算
    for (int i = cnt - 1; i >= 0; i--) {
        char op = tok[i][0];
        if (op == '+' || op == '-' ||
            op == '*' || op == '/') {
            double left = st[--top];    // 先弹出的是左操作数
            double right = st[--top];   // 后弹出的是右操作数
            double res = 0.0;
            if (op == '+') {
                res = left + right;
            } else if (op == '-') {
                res = left - right;
            } else if (op == '*') {
                res = left * right;
            } else {
                res = left / right;
            }
            st[top++] = res;
        } else {
            // 遇到操作数就压入栈中
            st[top++] = toDouble(tok[i]);
        }
    }
    // 栈里剩下的唯一一个数就是整个前缀表达式的值，保留两位小数输出
    cout.setf(ios::fixed);
    cout.precision(2);
    cout << st[0] << endl;
    return 0;
}

复杂度分析

设操作数有 $n$ 个，整个表达式最多有 $2n-1$ 个部分（数字和运算符）。从右往左扫描时每个部分只处理一次，入栈、出栈都是 $O(1)$，所以总时间 $O(n)$。空间上，栈里最多同时放 $n$ 个数，空间也是 $O(n)$。题目保证 $n\le500$，时间和空间都完全够用。