你好，同学！欢迎来到 NOI 数据结构专项训练。

今天我们要攻克的是一个在计算机科学和编译原理中极其经典的问题：逆波兰表达式求值。这道题不仅是“栈（Stack）”这一数据结构最核心的应用场景之一，也是理解表达式处理逻辑的基石。

---

一、 预备知识点

在动手之前，请确保你已经熟练掌握以下内容：

1. 逆波兰表达式（RPN）：又称后缀表达式。它的特点是操作符跟在操作数后面。例如 1 + 2 写成 1 2 +。它的优势是不需要括号就能表示运算优先级。
2. 栈（Stack）：后进先出（LIFO）的线性表。
3. 字符串与整数转换：在 C++ 中如何判断一个字符串是数字还是运算符，并将其转为整数（如 std::stoll 或 sscanf）。
4. 整数除法规则：在 C++11 及更高标准中，两个整数相除的结果向零截断（Truncate toward zero）。

---

二、 NOI 竞赛题目描述

题目名称：逆波兰表达式求值 (Evaluate Reverse Polish Notation) 时间限制：1.0s 内存限制：256MB

【问题描述】 给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式，并返回一个表示数值的整数。

有效的算符包括： +、-、*、/ 。 每个操作数可以是： 整数或者另一个表达式。 注意：

1. 两个整数之间的除法总是 向零截断。
2. 输入中不含除数为 0 的情况。
3. 答案及所有中间计算结果可以用 32 位 有符号整数表示（在 NOI 考场上，为了保险，建议使用 long long）。

【输入格式】 输入包含两行。 第一行是一个整数 $N$，表示表达式中 Token 的总数。 第二行包含 $N$ 个以空格分隔的 Token（字符串）。

【输出格式】 输出一个整数，表示表达式的计算结果。

【样例输入 1】

5
2 1 + 3 *

【样例输出 1】

9

解释：((2 + 1) * 3) = 9

【样例输入 2】

5
4 13 5 / +

【样例输出 2】

6

解释：(4 + (13 / 5)) = 6

【数据规模与约定】

• $1 \le N \le 10^4$
• 每个 Token 要么是一个运算符，要么是一个在范围 $[-200, 200]$ 内的整数。

---

三、 启发式思路引导：草稿纸上的推演

请拿出草稿纸，我们通过“托盘模拟法”来思考：

1. 核心矛盾：我们如何知道运算符该对谁操作？

在后缀表达式中，当你看到一个运算符（如 +）时，它总是作用于它紧邻的前面两个数字。

• 思考：当我们按顺序读取 2, 1, + 时，我们需要把 2 和 1 暂时存起来，等看到 + 时，再把最后存进去的两个数拿出来计算。
• 启发：这种“后存进去的先拿出来用”的特性，完美契合栈的逻辑。

2. 草稿纸模拟过程（以样例 2 为例）

表达式：4 13 5 / +

1. 读取 4：数字，压入栈。栈状态：(4)
2. 读取 13：数字，压入栈。栈状态：(4, 13)
3. 读取 5：数字，压入栈。栈状态：(4, 13, 5)
4. 读取 /：运算符。
   • 从栈顶弹出第一个数作为右操作数：B = 5
   • 从栈顶弹出第二个数作为左操作数：A = 13
   • 计算 A / B = 13 / 5 = 2
   • 将结果 2 压回栈。栈状态：(4, 2)
5. 读取 +：运算符。
   • 弹出 B = 2
   • 弹出 A = 4
   • 计算 A + B = 6
   • 压回栈。栈状态：(6)
6. 遍历结束：栈中最后剩下的数字 6 即为答案。

3. 易错点预警

• 减法与除法的顺序：栈顶弹出的第一个数是右操作数，第二个数才是左操作数。A / B 不能写反。
• 负数处理：Token 可能是一个负数（如 "-12"），判断“它是运算符还是负数”时，要注意 "-" 是运算符，而 "-12" 是数字。

---

四、 复杂度分析与优化建议

• 时间复杂度：$O(N)$。我们只需要遍历一次 Token 序列，每个元素入栈出栈各一次，操作均为 $O(1)$。
• 空间复杂度：$O(N)$。在最坏情况下（如全都是数字），栈需要存储所有 Token。
• 优化建议：
  1. 在 NOI 考场上，若 $N$ 很大，可以使用 std::vector 或手写数组来模拟栈，以获得更小的常数时间。
  2. 对于字符串转数字，std::stoll 比 stringstream 快得多。

---

五、 算法流程图（伪代码逻辑）

在 Mermaid 流程图中，我们描述 C++ 实现逻辑。

graph TD
    Start(开始处理 tokens 数组) --> Loop{遍历当前 token}
    Loop -- 遍历结束 --> Final(栈顶元素即为最终答案)
    Loop -- 是数字串 --> Push(将数字转为整数并入栈)
    Push --> Loop
    Loop -- 是运算符 op --> PopTwo(弹出栈顶两个元素 B 和 A)
    PopTwo --> Calc(计算 A op B)
    Calc --> PushRes(将计算结果压回栈)
    PushRes --> Loop

    subgraph Operation_Logic
    direction TB
    Plus(若 op 为加号: A 加 B)
    Minus(若 op 为减号: A 减 B)
    Mul(若 op 为乘号: A 乘 B)
    Div(若 op 为除号: A 除以 B)
    end

---

六、 读题关键词总结

在处理表达式求值类题目时，请重点圈出这些词：

1. “后缀” 或 “逆波兰” (RPN)：直接联想到栈操作。
2. “向零截断” (Truncate towards zero)：这是 C++ 默认的整数除法行为，但在某些语言或环境下（如向下取整）需要注意区分。
3. “操作数可以是整数或表达式”：意味着表达式具有递归嵌套性质，栈能完美处理这种层级关系。
4. “范围” (Range)：观察数值范围决定是否需要使用 long long 防止计算过程溢出。

教练寄语：后缀表达式是栈的本命题。掌握了“遇数入栈，遇符运算”这八字箴言，这类题目便迎刃而解。去尝试实现它吧！