CH BR4思考熊(恒等有理式-逆波兰表达式求值)

时间:2021-12-19 21:17:13

恒等有理式

总时限 10s 内存限制 256MB
出题人 fotile96 提交情况 4/43

描述

给定两个有理式f(X)与g(X),判断他们是否恒等(任意A,如果f(A)与g(A)均有定义,那么f(A)=g(A))。

有理式通过他们的中缀表达式给出,为了简化问题,我们对给出的中缀表达式进行如下的规范:

  1. 该表达式仅包含a-z0-9.+-*/^(),其中a-z用来表示未知数,0-9.用来表示数字常量,+-*/^是运算符,()用来改变运算顺序;
  2. 所有的运算符(+-*/^)都只作二元运算符使用,包括-;(即是说,-不被当作表示负数的单目运算符使用)
  3. 所有的运算符(+-*/^)都是左结合的,包括^;(即是说,^不是右结合的。x^a^b应当作(x^a)^b计算而不是x^(a^b))
  4. 表达式中的所有数字常量都是无符号的整数或者小数,即是说,是非空整数串或由.隔开的两个非空整数串,数字常量可能有前导零;
  5. 由于给出的是有理式,保证^的第二个运算数是自然数常量;
  6. 表达式中的未知数由小写字母a-z表示。

例如,下列的表达式在该规范下是合法的:

  • x^2+2*x+1
  • 1/(x+1)^2/(y+1)^2

而下面这些是不合法的:

  • -x^2-2*x-1
  • x^(4+5)
  • x^(0-1)

他们在这个约定下的可能的合法表示是:

  • 0-x^2-2*x-1
  • x^9
  • 1/x

输入格式

第一行,一个整数T,表示测试数据的组数。

接下来有T组数据,每组数据包含两行,每行给出了一个规范的有理式。

输出格式

对于每组数据输出一行,这行内的内容应当是"YES"或"NO"(不含引号),表示该组数据内的两个有理式恒等或是不等。

样例输入

4
(a+b)^2
a^2+2*a*b+b^2
1/x-1/y
(y-x)/(x*y)
x
x+0.00000000000001
0.0000000001*0.00000000001*x
(1/10)^21*x

样例输出

YES
YES
NO
YES

数据范围与约定

共10个测试点,每个测试点10分。每个测试点的总字符个数不超过6*10^5。另外,各个测试点满足:

  • 第1-3号测试点中不含小写英文字母
  • 第4-6号测试点,每个测试点总字符数不超过1000
  • 第7-10号测试点没有类似前两种数据的限制

完全不会做……

只好随便带数字进去骗……(不会……我X)

不想说什么了……(现学现卖:逆波兰表达式求值)

考虑到程序写得很清楚,不写过程了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define MAXN (600000+10)
typedef long long ll;
ll Fp[10]={1002347903,1000000411,1000000033,1000000087,1000000009};int p_size=5;
ll F=(1002347903);
int T,sp=0,opt[1000]={0},n;
ll val[1000]={0};
char buf[MAXN],st[MAXN];
ll num[MAXN];
ll pow2(ll a,ll b)
{
if (b==0) return 1;
if (b==1) return a%F;
ll c=pow2(a,b/2);
c=c*c%F;
if (b&1) c=c*a%F;
return c;
}
ll mulinv(ll a)
{
return pow2(a,F-2);
}
ll revF=mulinv(10);
ll getint(int &i)
{
if (st[sp]=='^') F--;//revF=mulinv(10); if (isalpha(buf[i])) return val[buf[i]];
ll xm=0,xr=1;
for(;isdigit(buf[i])&&i<=n;i++)
{
xm=(xm*10+(buf[i]-48))%F;
}
if (buf[i]=='.')
{
i++;
for(;isdigit(buf[i])&&i<=n;i++)
{
xm=(xm*10+(buf[i]-48))%F;xr=xr*revF%F;
}
}
i--; if (st[sp]=='^') F++;//revF=mulinv(10); return xm*xr%F;
}
void calc()
{
if (st[sp]=='+') num[sp]=(num[sp]+num[sp+1])%F;
else if (st[sp]=='-') num[sp]=(num[sp]-num[sp+1]+F)%F;
else if (st[sp]=='*') num[sp]=(num[sp]*num[sp+1])%F;
else if (st[sp]=='/') num[sp]=(num[sp]*mulinv(num[sp+1]))%F;
else if (st[sp]=='^') num[sp]=(pow2(num[sp],num[sp+1]))%F;
sp--;
}
void print()
{
if (T>=0) return;
//#ifdef DEBUG
For(j,sp+1) cout<<num[j]<<' ';cout<<endl;
For(j,sp) cout<<st[j]<<' ';cout<<endl;
cout<<"sp="<<sp<<endl;
//#endif
}
long long work()
{
n=strlen(buf+1);sp=0;
For(i,n)
{
// cout<<i<<':'<<endl;
int t=opt[buf[i]];
if (t>0)
{
while (opt[st[sp]]>=t) calc();
st[++sp]=buf[i];
}
else if (buf[i]=='(') st[++sp]=buf[i];
else if (buf[i]==')')
{
while (st[sp]!='(') calc();
num[sp]=num[sp+1];sp--;
}
else num[sp+1]=getint(i);
///-0000
print();
}
while (sp) calc(),print();
// cout<<"=================================================\n";
return num[1];
}
ll ans[10][2];
int main()
{
// freopen("expression.in","r",stdin);
// freopen(".out","w",stdout);
scanf("%d",&T);
// cout<<pow2(10,4);
// For(i,1000) cout<<pow2(10,i)<<' ';
/*
srand(32987);val['a']=1000000007;val['a']=1023492132;
For(i,25) val[i+'a']=(rand()*+rand()*10003+val[i+'a'-1])%F;
*/ srand('o'+'r'+'z');
For(i,26) val[i+'a'-1]=F-rand()%(F/100)-F/100*(i-1); // val['a']=1;val['b']=7;
opt['+']=opt['-']=1,opt['*']=opt['/']=2,opt['^']=3,opt['(']=opt[')']=-1;
while (T--)
{
Rep(j,2)
{
scanf("%s",buf+1);
Rep(i,5)
{
F=Fp[i];revF=mulinv(10);
ans[i][j]=work();
}
}
//cout<<ans[0][0]<<' '<<ans[0][1]<<endl;
bool bo=1;
Rep(i,5) if (ans[i][0]^ans[i][1]) {puts("NO");bo=0;break;}
if (bo) puts("YES");
}
return 0;
}