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：

说明

【提示】

仔细考虑不合法的情况，避免不必要的RE和WA。

【数据规模】

函数操作步数<=2000

询问数<=2000

思路：大模拟。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 100000

using namespace std;

string s[];

int tot,n;

int num[MAXN],stack[MAXN];

void gets(int x){

    tot++;

    cin>>s[x];

    if(s[x]=="END")    return ;

    if(s[x]=="NUM")    scanf("%d",&num[x]);

    gets(x+);

}

int main(){

    gets();

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        int opt,top=,flag=;

        scanf("%d",&opt);

        stack[++top]=opt;

        for(int j=;j<tot;j++){

            if(s[j]=="NUM"){

                if(num[j]>){ cout<<"ERROR"<<endl; flag=; break; }

                stack[++top]=num[j];

            }

            else if(s[j]=="POP"){

                if(top==){ cout<<"ERROR"<<endl; flag=; break; }

                top--;

            }

            else if(s[j]=="INV"){

                if(-stack[top]>){ cout<<"ERROR"<<endl; flag=;break; }

                stack[top]=-stack[top];

            }

            else if(s[j]=="DUP"){

                if(top==){ cout<<"ERROR"<<endl; flag=; break; }

                stack[++top]=stack[top-];

            }

            else if(s[j]=="SWP"){

                if(top<){ cout<<"ERROR"<<endl; flag=; break; }

                swap(stack[top],stack[top-]);

            }

            else if(s[j]=="ADD"){

                if(top<||stack[top]+stack[top-]>||stack[top]+stack[top-]<-){ cout<<"ERROR"<<endl; flag=; break; }

                stack[top-]=stack[top]+stack[top-];top--;

            }

            else if(s[j]=="SUB"){

                if(top<||stack[top-]-stack[top]>||stack[top-]-stack[top]<-){ cout<<"ERROR"<<endl; flag=; break; }

                stack[top-]=stack[top-]-stack[top];top--;

            }

            else if(s[j]=="MUL"){

                if(top<||stack[top]*stack[top-]>||stack[top]*stack[top-]<-){ cout<<"ERROR"<<endl; flag=; break; }

                stack[top-]=stack[top]*stack[top-];top--;

            }

            else if(s[j]=="DIV"){

                if(top<||stack[top-]==){ cout<<"ERROR"<<endl; flag=; break; }

                stack[top-]=stack[top]/stack[top-];top--;

            }

            else if(s[j]=="MOD"){

                if(top<||stack[top-]==){ cout<<"ERROR"<<endl; flag=; break; }

                stack[top-]=stack[top]%stack[top-];top--;

            }

        }

        if(flag)    continue;

        if(top!=){ cout<<"ERROR"<<endl; continue; }

        else cout<<stack[top]<<endl;

    }

}

50分代码

巴特西

P2186 小Z的栈函数

P2186 小Z的栈函数

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章