1 条题解
-
0
指令计算栈:讲解
思路与 STL 接口
stack 保存中间数。二元运算先读取 top 并 pop 得到 b,再得到 a,最后 push 结果;NEG 修改 top;DUP 把 top 的值 push 一份。使用 stoll 识别数字。C++17 整数除法向 0 取整。
复杂度
每个 token 执行 O(1) 次栈操作,总时间 O(n),空间 O(n)。范围保证结果和所有中间值都在 long long 内;乘法实际结果的绝对值≤10¹²。
常见错误
把弹出的第一项当成左操作数,减法与除法会反向;用 int 溢出;Python 对照若用 // 会向负无穷取整,须用整数绝对值除法后恢复符号。
验证方法
Python oracle 独立读取操作并模拟或排序,不调用标准程序。正式数据含手算样例、边界、固定种子随机和两个最大规模用例;另做 200 次小规模差分,验证器拒绝非法状态和多余 token。common_wrong.cpp 保留上述一种常见逻辑错误,正式数据必须能够拒绝它。
C++17 参考实现
#include <bits/stdc++.h> using namespace std; int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;stack<long long>s;while(n--){string t;cin>>t;if(t=="NEG")s.top()=-s.top();else if(t=="DUP")s.push(s.top());else if(t=="+"||t=="-"||t=="*"||t=="/"){long long b=s.top();s.pop();long long a=s.top();s.pop();if(t=="+")s.push(a+b);else if(t=="-")s.push(a-b);else if(t=="*")s.push(a*b);else s.push(a/b);}else s.push(stoll(t));}cout<<s.top()<<'\n';}
- 1
信息
- ID
- 5258
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者