P4819 后缀表达式的值（基础）

解题思路

1. 后缀表达式怎么求值。 后缀表达式把运算符写在两个操作数后面，比如 16 9 4 3 + * - 表示 16 - 9*(4+3)。求值规则非常机械：从左到右扫描，遇到数字就压入栈，遇到运算符就弹出两个数字，算出结果再压回栈。扫描完后栈里剩下的唯一数字就是答案。
2. 逐字符读入。 输入以 @ 结束，数字之间用空格隔开。用 cin.get 一次读一个字符：如果是数字字符，就累加拼成一个整数 num；如果是空格或换行，说明一个数字读完了，把 num 压入栈并清零；如果是运算符 + - * /，就弹出两个数计算。
3. 千万别搞反顺序。 弹出时，先弹出的是右操作数，后弹出的是左操作数。做减法要 left - right，做除法要 left / right。顺序反了，16-63 就会变成 63-16，答案就错了。
4. 多位数要拼起来。 比如 16 是两位数字，要先把 '1' 和 '6' 拼成 16 再压栈，不能把 1 和 6 分别当两个数。
5. 用 long long。 题目说参与运算的整数和结果都在 64 位整数范围内，用 long long 存储最稳妥，乘法和加法都不会溢出。

参考代码

// 后缀表达式的值：读入以@结尾的后缀表达式，遇到数字压栈，遇到运算符弹出两个数计算后压回栈
#include <iostream>
using namespace std;

int main() {
    long long stack[260];   // 运算数栈
    int top = 0;
    long long num = 0;      // 正在读入的一个整数
    bool reading = false;   // 当前是否正在读数字
    char ch;
    while (cin.get(ch)) {
        if (ch == '@') break;   // @ 是表达式结束标志
        if (ch >= '0' && ch <= '9') {
            num = num * 10 + (ch - '0');
            reading = true;
        } else if (ch == ' ' || ch == '\n') {
            if (reading) {   // 读完一个完整的数，压入栈
                stack[top++] = num;
                num = 0;
                reading = false;
            }
        } else {
            // 遇到运算符：先把可能还没压栈的数压进去，再弹出两个操作数计算
            if (reading) {
                stack[top++] = num;
                num = 0;
                reading = false;
            }
            long long right = stack[--top];   // 先弹出的是右操作数
            long long left = stack[--top];    // 后弹出的是左操作数
            if (ch == '+') stack[top++] = left + right;
            else if (ch == '-') stack[top++] = left - right;
            else if (ch == '*') stack[top++] = left * right;
            else if (ch == '/') stack[top++] = left / right;
        }
    }
    cout << stack[top - 1] << endl;   // 栈底（最后一个元素）就是表达式的值
    return 0;
}

复杂度分析

每个字符被处理一次，每个数字和运算符各进栈出栈一次，所以时间复杂度是 O(len)，len 是输入字符串长度（小于 250）。空间上需要一个长度 260 的数组当栈，是 O(len)。整个算法飞快，即使有几百个运算符也不怕。