Luogu P2186 小Z的栈函数
[toc]
题目
【题目描述】
小Z最近发现了一个神奇的机器，这个机器的所有操作都是通过维护一个栈来完成的，它支持如下11个操作：
NUM X：栈顶放入X。
POP：抛弃栈顶元素。
INV：将栈顶元素取出，然后放入它的相反数。
DUP：再放入一个和栈顶元素相同的数。
SWP：交换栈顶的两个元素。
ADD：取出栈顶的两个元素，两元素相加，所得结果放入栈内。
SUB：取出栈顶的两个元素，第二个元素减去第一个元素，所得结果放入栈内。
MUL：取出栈顶的两个元素，两元素相乘，所得结果放入栈内。
DIV：取出栈顶的两个元素，第二个元素整除以第一个元素，所得结果放入栈内。
MOD：取出栈顶的两个元素，第二个元素取模以第一个元素，所得结果放入栈内。
END：结束这个程序。
然后，小Z用上面的11种操作写了一个一元函数f(x)。x就是放入栈里面第一个初始元素。然后经过这个函数的一系列操作，当函数结束的时候，正常情况下，栈里面会有唯一的一个元素。剩下的这个元素就作为函数f(x)的返回值。
小Z有N个询问，询问每个值x经过上述函数所映射出的f(x)是多少。但是这个由于机器太老了，跑起东西来太慢了，小Z又是一个急性子，所以请你们写一个程序，来帮助小Z计算他查询的f(x)。
【输入输出格式】
输入格式：
输入若干行，仅包含上述11个操作，用来描述函数f(x)的操作，函数的结束保证以END结尾；
接下来一个整数N；
下面N行每行一个数字ai，代表栈里面的初始元素。
输入数据不保证合法！！！
输出格式：
如果最后栈内不是一个元素，输出“ERROR”；
还有，由于这台机器太破了，所以如果运算过程中有数字的绝对值大于1000000000机器也输出“ERROR”；
如果输入数据不合法，导致中途退出，输出“ERROR”；
否则输出对应的f(x)。
【输入输出样例】
输入样例#1：
NUM 600000000
ADD
END
3
0
600000000
1
输出样例#1：
600000000
ERROR
600000001
思路
没啥好说的，就是模拟
注意ERROR情况：
- 栈空了还要访问栈顶元素
- 栈顶元素或运算结果绝对值大于1e9
- 最后的结果栈不只有1个元素或者没有元素
- 除以0或者模0
用一个flag记录一下当前操作是否合法就行了。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<string>
#include<algorithm>
#define ll long long
//#define FILE freopen("stack.in","r",stdin);freopen("stack.out","w",stdout);
using namespace std;
stack<ll> s;
inline bool num(ll x) { //NUM X：把X这个元素放置栈顶。
if(abs(x)>1e9)
return 0;
s.push(x);
return 1;
}
inline bool pop() { //POP X：抛弃栈顶元素。
if(s.empty())
return 0;
s.pop();
return 1;
}
inline bool inv() { //INV：将栈顶元素取出，然后放入它的相反数。
if(s.empty())
return 0;
ll x=s.top();
if(abs(x)>1e9)
return 0;
s.pop();
s.push(-x);
return 1;
}
inline bool dup() { //DUP：再放入一个和栈顶元素相同的数。
if(s.empty())
return 0;
ll x=s.top();
if(abs(x)>1e9)
return 0;
s.push(x);
return 1;
}
inline bool swp() { //SWP：交还栈顶的两个元素。
if(s.empty())
return 0;
ll x=s.top();
s.pop();//顶
if(s.empty() || abs(x)>1e9)
return 0;
ll y=s.top();
s.pop();//次顶
if(abs(y)>1e9)
return 0;
s.push(x);
s.push(y);
return 1;
}
inline bool add() { //ADD：将栈顶的两个元素相加然后放入栈内。
if(s.empty())
return 0;
ll x=s.top();
s.pop();//顶
if(s.empty() || abs(x)>1e9)
return 0;
ll y=s.top();
s.pop();//次顶
if(abs(y)>1e9 || abs(x+y)>1e9)
return 0;
s.push(x+y);
return 1;
}
inline bool sub() { //SUB：取出栈顶的两个元素，第二个元素减去第一个元素，所得结果放入栈内。
if(s.empty())
return 0;
ll x=s.top();
s.pop();//顶 1
if(s.empty() || abs(x)>1e9)
return 0;
ll y=s.top();
s.pop();//顶 2
if(abs(y)>1e9 || abs(y-x)>1e9)
return 0;
s.push(y-x);
return 1;
}
inline bool mul() { //MUL：将栈顶的两个元素相乘然后放入栈内。
if(s.empty())
return 0;
ll x=s.top();
s.pop();//顶 1
if(s.empty() || abs(x)>1e9)
return 0;
ll y=s.top();
s.pop();//顶 2
if(abs(y)>1e9 || abs(y*x)>1e9)
return 0;
s.push(y*x);
return 1;
}
inline bool div() { //DIV：取出栈顶的两个元素，第二个元素整除以第一个元素，所得结果放入栈内。
if(s.empty())
return 0;
ll x=s.top();
s.pop();//顶 1
if(s.empty() || abs(x)>1e9)
return 0;
ll y=s.top();
s.pop();//顶 2
if(abs(y)>1e9 || x==0 ||abs(y/x)>1e9)
return 0;
s.push(y/x);
return 1;
}
inline bool mod() { //MOD：取出栈顶的两个元素，第二个元素取模以第一个元素，所得结果放入栈内。
if(s.empty())
return 0;
ll x=s.top();
s.pop();//顶 1
if(s.empty() || abs(x)>1e9)
return 0;
ll y=s.top();
s.pop();//顶 2
if(abs(y)>1e9 || abs(y%x)>1e9)
return 0;
s.push(y%x);
return 1;
}
char ord[2005][10];
ll cnt=0;
ll Num[2005]= {0};
ll Ncnt=0;
ll n;
int main() {
ios::sync_with_stdio(false);
// FILE;
while(cin>>ord[++cnt]) {
if(ord[cnt][0]=='E')
break;
if(ord[cnt][0]=='N')
cin>>Num[++Ncnt];
}
cin>>n;
while(n--) {
while(!s.empty()) s.pop();
ll a;
ll j=1;
cin>>a;
if(abs(a)>1e9) {
cout<<"ERROR\n";
continue;
}
s.push(a);
bool flag=1;
for(ll i=1; i<cnt; i++) {
//cout<<ord[i]<<endl;
if(flag==0)
break;
if(ord[i][0]=='N')
flag=flag && num(Num[j++]);
if(ord[i][0]=='P')
flag=flag && pop();
if(ord[i][0]=='I')
flag=flag && inv();
if(ord[i][0]=='D' && ord[i][1]=='U')
flag=flag && dup();
if(ord[i][0]=='S' && ord[i][1]=='W')
flag=flag && swp();
if(ord[i][0]=='A' && ord[i][1]=='D')
flag=flag && add();
if(ord[i][0]=='S' && ord[i][1]=='U')
flag=flag && sub();
if(ord[i][0]=='M' && ord[i][1]=='U')
flag=flag && mul();
if(ord[i][0]=='D' && ord[i][1]=='I')
flag=flag && div();
if(ord[i][0]=='M' && ord[i][1]=='O')
flag=flag && mod();
}
if(s.empty() || flag==0) {
cout<<"ERROR\n";
continue;
}
ll ans=s.top();
s.pop();
if(flag==0 || !s.empty() || abs(ans)>1e9) {
cout<<"ERROR\n";
continue;
} else
cout<<ans<<endl;
}
return 0;
}