题目描述
明明进了中学之后,学到了代数表达式。
有一天,他碰到一个很麻烦的选择题。
这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。
这个题目手算很麻烦,因为明明对计算机编程很感兴趣,所以他想是不是可以用计算机来解决这个问题。
假设你是明明,能完成这个任务吗?
这个选择题中的每个表达式都满足下面的性质:
表达式只可能包含一个变量‘a’。
表达式中出现的数都是正整数,而且都小于10000。
表达式中可以包括四种运算‘+’(加),‘-’(减),‘’(乘),‘^’(乘幂),以及小括号‘(’,‘)’。小括号的优先级最高,其次是‘^’,然后是‘’,最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。(注意:运算符‘+’,‘-’,‘*’,‘^’以及小括号‘(’,‘)’都是英文字符)
幂指数只可能是1到10之间的正整数(包括1和10)。
表达式内部,头部或者尾部都可能有一些多余的空格。
数据中所有的表达式一定是合法的,例如左右括号一定是相互匹配的。(NOIP原始数据有误,存在左右括号不匹配的情况,我们对错误数据进行了修正,可不必考虑括号不匹配情况)
下面是一些合理的表达式的例子:
((a^1) ^ 2)^3,aa+a-a,((a+a)),9999+(a-a)a,1 + (a -1)^3,1^10^9……
样例输入
( a + 1) ^2
3
(a-1)^2+4*a
a + 1+ a
a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a
样例输出
AC
思路:
很多人决定用特殊代值的方法,我觉得很low
所以我直接打了个大模拟
直接将每一个式子给化简合并与初始式子比较每一位
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=80,mod=1e9+7;
string opq;int fu,endd;
struct node{
long long num[10000];//代表a的指数是i的项的系数是多少
node operator + (node b){//重载加号
node a=*this,c;
memset(c.num,0,sizeof(c.num));
for(int i=0;i<=N;i++){
c.num[i]=(a.num[i]+b.num[i])%mod;
}
return c;
}
node operator * (node b){//重载乘号
node a=*this,c;
memset(c.num,0,sizeof(c.num));
for(int i=0;i<=N;i++){
for(int j=0;j<=N;j++){
c.num[i+j]=(c.num[i+j]+a.num[i]*b.num[j]%mod)%mod;//同底数幂想乘,指数相加,系数相乘,
}
}
return c;
}
node operator ^ (int b){
node a=*this,c;
memset(c.num,0,sizeof(c.num));
c.num[0]=1;
for(int i=1;i<=b;i++){//反正幂不超过10,就直接循环乘
c=c*a;
}
return c;
}
node operator - (node b){
node a=*this,c;
memset(c.num,0,sizeof(c.num));
for(int i=0;i<=N;i++){
c.num[i]=(a.num[i]-b.num[i])%mod;//减法
}
return c;
}
}frist,look;//frist是初始式子,look是输入的比较式子
int n;
node sr();
node gets();
node find();
int main(){
// freopen("equal.in","r",stdin);
// freopen("equal.out","w",stdout);
getline(cin,opq);//直接读入一行
frist=find();
cin>>n;
int flag[100];int times=0;
memset(flag,0,sizeof(flag));
getchar();//将换行符给取出
while(n--){
getline(cin,opq);endd=opq.size();fu=0;//fu是当前计算到opq的第几个位置
memset(look.num,0,sizeof(look.num));//初始化数组
look=find();flag[times]=1;
for(int i=0;i<=N;i++){//比较
if(look.num[i]!=frist.num[i]){
flag[times]=0;
break;
}
}
times++;
}
for(int i=0;i<N;i++){
if(flag[i]){
cout<<(char)(i+'A');//强制类型转换
}
}
return 0;
}
node sr(){
char k;int x=0;node help,mmp;
memset(help.num,0,sizeof(help.num));
k=opq[fu];//将k当前字符取出
// if(k=='/n') return help;
if(k==' '){
fu++;
k=opq[fu];
}
if(k=='('){//若有括号则优先计算括号内的项数
fu++;
help=find();//计算;
k=opq[fu];//取出下括号后一个字符的值
fu++;
k=opq[fu];
if(k==' '){//一定要去出空格影响
fu++;
k=opq[fu];
}while(k=='^'){//若括号后有乘方,直接对括号内的值进行乘方
fu++;
k=opq[fu];
int awsl=0;
while(k>='0'&&k<='9'){//寻找幂的指数
fu++;
awsl*=10;
awsl+=k-'0';
k=opq[fu];
}
help=help^(awsl);
}
return help;//直接将幂次方给返回
}
while(k=='a'){//若当前字符是未知数,这其当前的指数一定是1
help.num[1]++;
fu++;
k=opq[fu];
}
while((k<='9'&&k>='0')){//若输入数字
x*=10;
x+=k-'0';
fu++;
k=opq[fu];
}
if(k==' '){//取空格
fu++;
k=opq[fu];
}
help.num[0]=x;//将数字给赋到a^0的系数上
while(k=='^'){//乘方优先级最大可直接在此计算
fu++;
k=opq[fu];
int awsl=0;
while(k>='0'&&k<='9'){
fu++;
awsl*=10;
awsl+=k-'0';
k=opq[fu];
}
help=help^(awsl);
}
return help;
}
node gets(){//计算乘法
node help,reve;
memset(help.num,0,sizeof(help.num));
memset(reve.num,0,sizeof(reve));
help=sr();
char f=opq[fu];
if(f==' '){
fu++;
f=opq[fu];
}
while(f=='*'){
if(f=='*'){
fu++;
reve=sr();
help=help*reve;
f=opq[fu];
if(f==' '){//取空格
fu++;
f=opq[fu];
}
}
}
return help;
}
node find(){
node help,reve;//寻找当前的项数
// system("pause");
memset(help.num,0,sizeof(help.num));
memset(reve.num,0,sizeof(reve));
help=gets();
char f=opq[fu];
if(f==' '){
fu++;
f=opq[fu];
}
while(f=='+'||f=='-'){
if(f=='+'){
fu++;
reve=gets();
help=help+reve;
f=opq[fu];
if(f==' '){
fu++;
f=opq[fu];
}
}
else if(f=='-'){
fu++;
reve=gets();
help=help-reve;
f=opq[fu];
if(f==' '){
fu++;
f=opq[fu];
}
}
}
return help;
}
手写CAS%%%%
en。。。我还是选择待特殊值法,
或者不做I agree with you
何low之有?
极其之low
打完一道大模拟感觉人都精神了
为什么有简单的方法不用,偏要硬刚…