P4822 后缀表达式求值（基础）

解题思路

这道题要我们计算后缀表达式（也叫逆波兰式）的值。后缀表达式把运算符写在两个数的后面，比如 14 3 20 5 / * 8 - +，算出来是 18。

第一步，理解后缀表达式怎么算。 从左往右扫：遇到数字就压进栈；遇到运算符，就弹出栈顶的两个数，算出结果再压回栈。所有部分扫描完，栈里剩下的唯一一个数就是答案。

第二步，注意弹出顺序。 先弹出的是右边那个数，后弹出的是左边那个数。比如 20 5 /，先弹出 5、后弹出 20，算的是 $20/5$。如果顺序搞反，减法 3 4 - 会算成 $4-3=1$ 而不是 $3-4$，答案就错了。

第三步，除法是整除。 题目特别强调：遇到除法只算整除的结果，不要小数。C++ 里两个 int 相除本来就是整除，比如 $20/5=4$，直接除就行，不用额外处理。

第四步，拿样例走一遍。 14 3 20 5 / * 8 - + @：依次读到 14、3、20、5 入栈；/ 弹出 5 和 20 得 4 入栈；* 弹出 4 和 3 得 12 入栈；8 入栈；- 弹出 8 和 12 得 4 入栈；+ 弹出 4 和 14 得 18。碰到 @ 停止，输出 18。

第五步，@ 表示输入结束。 每个数字和符号之间都有空格，用 cin >> 一次读一个部分，读到字符 @ 就停止循环。数据范围保证中间结果在 $0\sim10^8$ 内，用 int 不会溢出。

参考代码

// 用途：计算后缀表达式（逆波兰式）的值，整数运算，除法只取整除结果
#include <iostream>
using namespace std;

// 数值栈，保存运算中的整数
int st[500];
int top = 0;

int main() {
    char tok[20];
    while (cin >> tok) {
        // '@' 表示输入结束
        if (tok[0] == '@') {
            break;
        }
        if (tok[0] == '+' || tok[0] == '-' ||
            tok[0] == '*' || tok[0] == '/') {
            // 弹出两个操作数，先弹出的是右操作数，后弹出的是左操作数
            int right = st[--top];
            int left = st[--top];
            int res = 0;
            if (tok[0] == '+') {
                res = left + right;
            } else if (tok[0] == '-') {
                res = left - right;
            } else if (tok[0] == '*') {
                res = left * right;
            } else {
                res = left / right;  // 整除
            }
            st[top++] = res;
        } else {
            // 把字符串形式的数字转成整数后入栈
            int val = 0;
            for (int i = 0; tok[i] >= '0' && tok[i] <= '9'; i++) {
                val = val * 10 + (tok[i] - '0');
            }
            st[top++] = val;
        }
    }
    // 栈里剩下的唯一一个数就是表达式的值
    cout << st[0] << endl;
    return 0;
}

复杂度分析

设表达式里的数字有 $n$ 个。每个数字入栈一次，每个运算符弹出两个数、算一次，所有部分只被处理一遍，所以时间是 $O(n)$。空间上，栈最多同时放 $n$ 个数，也是 $O(n)$。题目里数字不超过几百个，运行飞快。