题解 P2186 【小Z的栈函数】

· · 题解

做了一下午，一次就 AC。

先总结一下坑点&RE原因：

  1. 开 long\space long，万年老坑。

  2. DIV操作一定要判断除数是否为 0。

  3. 输入的 x 一定要 push 到栈里卡了我 \sout{1h}。

接下来就是万恶的模拟了：

先看输入部分：

可以将 step 数组来记录操作序列，num 来记录 NUM 操作中的 x，当然，cnt 要记录操作的次数，一直输入直到碰到END操作。

然后便是函数 f(x)，按照题意模拟即可，不过对于有加减乘除的操作，一定要判断结果是否大于 1000000000，若大于，我的做法是将此函数返回一个特殊值。另外，在取栈顶元素时，要先判断一下栈内元素是否足够。

最后就是代码惹：

#include<cstdio>
#include<stack>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;//开long long 
const int MAXN=2010;
string step[MAXN];//操作序列 
ll n,num[MAXN],x,cnt;
//n，NUM操作的x，输入的x，操作总数。 
stack<ll>st;//STL大法吼！ 
inline ll read()//快读 
{
    ll s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
    return s*w;
}
bool check(ll x)//判断x是否超出范围 
{
    return abs(x)>1000000000;
}
ll error()//懒
{
    printf("ERROR\n");
    return 5201314;//这是特殊值。 
}
ll f(ll x)//f函数 
{
    while(!st.empty()) st.pop();//先清空栈 
    st.push(x);//一定要push！ 
    for(register ll i=1;i<cnt;i++)//从头到尾(cnt-1)遍历操作序列 
    {
        //下面就不细说了 
        if(step[i]=="NUM")
        {
            if(check(num[i])) return error();
            st.push(num[i]);
        }
        if(step[i]=="POP")
        {
            if(st.empty()) return error();
            st.pop();
         } 
        if(step[i]=="INV")
        {
            if(st.empty()) return error();
            ll now=-st.top();
            st.pop();
            st.push(now);
        }
        if(step[i]=="DUP")
        {
            if(st.empty()) return error();
            ll now=st.top();
            st.push(now);
        }
        if(step[i]=="SWP")
        {
            if(st.size()<2) return error();
            ll x1=st.top();
            st.pop();
            ll x2=st.top();
            st.pop();
            st.push(x1);
            st.push(x2);
        }
        if(step[i]=="ADD")
        {
            if(st.size()<2) return error();
            ll x1=st.top();
            st.pop();
            ll x2=st.top();
            st.pop();
            ll ans=x1+x2;
            if(check(ans)) return error();
            st.push(ans);
        }
        if(step[i]=="SUB")
        {
            if(st.size()<2) return error();
            ll x1=st.top();
            st.pop();
            ll x2=st.top();
            st.pop();
            ll ans=x2-x1;
            if(check(ans)) return error();
            st.push(ans);
        }
        if(step[i]=="MUL")
        {
            if(st.size()<2) return error();
            ll x1=st.top();
            st.pop();
            ll x2=st.top();
            st.pop();
            ll ans=x1*x2;
            if(check(ans)) return error();
            st.push(ans);
        }
        if(step[i]=="DIV")
        {
            if(st.size()<2) return error();
            ll x1=st.top();
            st.pop();
            ll x2=st.top();
            st.pop();
            if(x1==0) return error();//一定要判除数！ 
            ll ans=x2/x1;
            if(check(ans)) return error();
            st.push(ans);
        }
        if(step[i]=="MOD")
        {
            if(st.size()<2) return error();
            ll x1=st.top();
            st.pop();
            ll x2=st.top();
            st.pop();
            ll ans=x2%x1;
            if(check(ans)) return error();
            st.push(ans);
        }
    }
    if(st.size()!=1) return error();//看看栈的最后大小 
    else return st.top();
}
int main()
{
    for(cnt=1;;cnt++)
    {
        cin>>step[cnt];
        if(step[cnt]=="NUM") num[cnt]=read();
        if(step[cnt]=="END") break;
    }
    n=read();
    for(register ll i=1;i<=n;i++)
    {
        x=read();
        x=f(x);
        if(x!=5201314) printf("%lld\n",x);//输出 
    }
    return 0;//完结撒花~~ 
}

点个赞再走呗QAQ