[洛谷]P2186 小Z的栈函数
题目描述
小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
说明
【提示】
仔细考虑不合法的情况，避免不必要的RE和WA。
【数据规模】
函数操作步数<=2000
询问数<=2000
思路
模拟
ERROR：
- y div x中x==0 && y mod x中x==0
- 取数前stack为empty
代码
#include <iostream>
#include <cstdio>
#include <stack>
#include <cmath>
#include <cstring>
using namespace std;
const int maxnum=1e9;
stack<int>st;
int n;int cnt=0;
int initnum[2010];
bool flag;
string op[2010];
inline void jud(long long x)
{
if(abs(x)>maxnum)
{
flag=true;
return;
}
}
void num(int x)
{
jud(initnum[x]);
st.push(initnum[x]);
return;
}
void pop()
{
st.pop();
return;
}
void inv()
{
if(st.empty())
{
flag=true;
return;
}
int tmp=st.top();st.pop();
jud(tmp);
st.push(-tmp);
return;
}
void dup()
{
if(st.empty())
{
flag=true;
return;
}
int tmp=st.top();
jud(tmp);
st.push(tmp);
return;
}
void swp()
{
if(st.empty())
{
flag=true;
return;
}
int x,y;
x=st.top();st.pop();
jud(x);
y=st.top();st.pop();
jud(y);
st.push(x);
st.push(y);
return;
}
void add()
{
int x,y;
if(st.empty())
{
flag=true;
return;
}
x=st.top();st.pop();
if(st.empty())
{
flag=true;
return;
}
y=st.top();st.pop();
jud(x+y);
st.push(x+y);
return;
}
void sub()
{
int x,y;
if(st.empty())
{
flag=true;
return;
}
x=st.top();st.pop();
if(st.empty())
{
flag=true;
return;
}
y=st.top();st.pop();
jud(y-x);
st.push(y-x);
return;
}
void mul()
{
int x,y;
if(st.empty())
{
flag=true;
return;
}
x=st.top();st.pop();
if(st.empty())
{
flag=true;
return;
}
y=st.top();st.pop();
jud(x*y);
st.push(x*y);
return;
}
void div()
{
int x,y;
if(st.empty())
{
flag=true;
return;
}
x=st.top();st.pop();
if(st.empty())
{
flag=true;
return;
}
y=st.top();st.pop();
if(x==0 || abs(y/x)>maxnum)
{
flag=true;
return;
}
st.push(y/x);
return;
}
void mod()
{
int x,y;
if(st.empty())
{
flag=true;
return;
}
x=st.top();st.pop();
if(st.empty())
{
flag=true;
return;
}
y=st.top();st.pop();
if(x==0 && abs(y%x)>maxnum)
{
flag=true;
return;
}
st.push(y%x);
return;
}
int main()
{
while(1)
{
cin>>op[++cnt];
if(op[cnt]=="END") break;
if(op[cnt]=="NUM") cin>>initnum[cnt];
}
cin>>n;
while(n--)
{
while(!st.empty()) st.pop();
int x;
cin>>x;
if(abs(x)>maxnum)
{
cout<<"ERROR"<<endl;
continue;
}
st.push(x);
flag=false;
for(int i=1;i<=cnt;i++)
{
if(flag) break;
if(op[i]=="END") break;
if(op[i]=="NUM") num(i);
if(op[i]=="POP") pop();
if(op[i]=="INV") inv();
if(op[i]=="DUP") dup();
if(op[i]=="SWP") swp();
if(op[i]=="ADD") add();
if(op[i]=="SUB") sub();
if(op[i]=="MUL") mul();
if(op[i]=="DIV") div();
if(op[i]=="MOD") mod();
}
if(flag || st.size()>1) cout<<"ERROR"<<endl;
else cout<<st.top()<<endl;
}
return 0;
}