学习目标
- 用操作数栈处理以空白分隔的有符号整数和四则运算。
- 保持减法、除法的左右操作数顺序，并约定除零及栈数量错误。
- 分析每个 token 恰好处理一次的复杂度。
前置知识与环境
建议先学习第 2 章栈与队列。使用 ISO C++17；开始前可在本目录运行 make doctor。
任务
按顺序读取 token。整数入栈；二元运算符弹出两个数：先弹出的是右操作数，再弹出的是左操作数。计算 left op right 并将结果入栈。除法采用 C++ 整数除法，即向零截断，例如 -7 / 3 = -2。
输入格式
第一行 token 数 n；第二行包含恰好 n 个、以空白分隔的整数或 + - * / token；当 n=0 时第二行为空。
输出格式
全部 token 处理结束后，栈恰有一个结果则输出该整数；否则输出 ERROR。遇到不认识的 token、操作数不足或除数为零也输出 ERROR。n=0 时输出 ERROR。每次运算结果保证在 64 位有符号范围内。
例如输入 5 和 2 1 + 3 *，先求 2+1=3，再求 3*3=9，输出 9。输入 3 和 8 3 - 输出 5，不是 -5。
数据范围与限制
- 输入规模不超过
200000，除题面另有说明外整数使用 64 位有符号范围。 0 <= n <= 200000；每个操作数和每次运算结果都必须落在 64 位有符号整数范围内，保证不会发生溢出。- 除数为
0、操作数不足或最终栈中不是恰好一个结果时，输出ERROR。 - 标准输出只保留题目要求的结果；调试信息写入标准错误。
- 目标算法应为线性或摊还线性时间，辅助空间不超过
O(n)。
边界与验收重点
- 单个整数就是答案；空表达式和末尾剩余多个数均输出
ERROR。 1 +操作数不足；3 0 /除零；负数 token-3不等同于减号-。- 先记录右操作数，再记录左操作数，不能交换减法或除法的顺序。
如何验证
powershell
make doctor
make run
make score未安装 Make 时，在仓库根目录运行：
powershell
pnpm lab:validate -- labs/chapter-02/exercise/E-02-10-rpn-evaluation
pnpm lab:run -- labs/chapter-02/exercise/E-02-10-rpn-evaluation
pnpm lab:score -- labs/chapter-02/exercise/E-02-10-rpn-evaluation思考与复盘
- 为什么弹出的第一个数字是右操作数？
- 为什么只验证过程中从未出现空栈还不够？
思考题参考
- 后缀式的运算符紧跟两个操作数之后，后入栈的数属于运算符右侧。
1 2全程没有弹空，但结束时有两个结果，不是完整表达式。
题解
点击查看题解
思路与不变量
用栈保存已经读到、尚未参与后续运算的操作数。读到整数就入栈；读到运算符就弹出右操作数和左操作数，计算 left op right 后把结果压回。处理每个 token 后，栈保存的始终是当前前缀中尚未归约的结果。
算法步骤
- 读取
n个 token，并逐个判断是整数还是运算符； - 整数入栈；运算符要求栈中至少有两个数，先弹出右数、再弹出左数；
- 检查运算符合法且除数非零，计算后将结果入栈；
- 全部 token 处理完后，只有栈中恰有一个值且过程中没有错误时才输出该值，否则输出
ERROR。
正确性说明
后缀表达式的运算符对应它前面的两个操作数，后入栈的数位于运算符右侧，所以弹出顺序必须是右、左。每次合法归约都把一个完整子表达式替换为其值；结束时恰有一个值，正好表示完整表达式，否则说明存在缺少操作数、剩余多个表达式或其他非法情况。
复杂度分析
- 时间复杂度：
O(n)，每个 token 入栈或参与一次出栈归约； - 额外空间：
O(n)，栈最多保存线性数量的操作数。
边界注意
n=0、操作数不足、最终栈大小不为 1 都输出ERROR；-3是整数 token，单独的-才是减法运算符；- 除法遵循 C++ 向零截断规则，除数为零必须在运算前判错。