#STL005. 指令计算栈

指令计算栈

指令计算栈

计算台只有一个初始为空的栈。操作员提交一串数字与指令:数字入栈,指令从栈顶取数并把结果放回栈顶。请计算执行完成后的唯一结果。

输入格式

第一行是 token 数 n。随后给出 n 个用空白分隔的 token。token 为整数或 +、-、*、/、NEG、DUP;单独的 - 表示减法,形如 -7 的 token 表示负整数。

操作与输出格式

输出最终栈中的唯一整数。数字 token 直接入栈。二元指令先弹出右操作数 b,再弹出左操作数 a,计算 a+b、a−b、a×b 或 a÷b;除法向 0 取整,例如 −7÷3=−2。NEG 把栈顶取负,DUP 复制栈顶并压入一份副本。

数据范围

1 ≤ n ≤ 200000;数字 token 在 [−10⁹,10⁹] 内。保证每条指令都有足够的操作数,除数不为 0,每一步所有栈中数的绝对值不超过 10¹²,最终恰好剩一个数。使用 64 位有符号整数保存中间值。

时间限制:2000 ms;内存限制:256 MiB。输出按空白分隔的词比较。

样例 1

输入:

7
8 3 - DUP * 2 /

输出:

12

解释:8−3=5,复制后相乘得到 25,25÷2 向 0 取整为 12。

样例 2

输入:

10
-7 3 / NEG 5 - DUP 4 * +

输出:

-15

解释:−7÷3=−2,取负得 2;2−5=−3,复制后将一份乘 4 得 −12,两份相加为 −15。

创作记录

题面、样例、实现与数据由本题制作组依照公开的 C++ 标准库概念独立撰写,未使用第三方题面、故事、测试文件或程序。