1686.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"string.h"
long n[100];
char f[100];
char b[100];
int ns,fs,bs;
long sjs[10]={0,1,17,47,13,43,7,97,319,67};

inline long find(int begin,char c)
{int i;
if(c>='A'&&c<='Z')c=c-'A'+'a';
for(i=0;i<bs;i++)if(b[i]==c)break;
if(i<bs)return sjs[(begin+i)%10];

b[bs++]=c;

return sjs[(begin+i)%10];
}

long js(char *p,int begin,int key)
{int i=0;long x,y;
ns=0;fs=0;if(key==0)bs=0;


while(p[i]!=0)
{

switch(p[i])
{case '(':f[fs++]='(';break;
 case '*':if(fs>0&&f[fs-1]=='*'){y=n[--ns];x=n[--ns];
		n[ns++]=x*y;
		fs--;}
	f[fs++]='*';
	break;
case '+':case '-':
case ')':case '#':if(fs==0){f[fs++]=p[i];break;}
		if(f[fs-1]!='('){y=n[--ns];x=n[--ns];
			if(f[fs-1]=='+')n[ns++]=x+y;
			if(f[fs-1]=='-')n[ns++]=x-y;
			if(f[fs-1]=='*')n[ns++]=x*y;	
			fs--;
			}
		if(fs>0&&f[fs-1]=='('&&p[i]==')')fs--;
		if(p[i]=='+'||p[i]=='-')f[fs++]=p[i];
		break;
default :if(p[i]>='0'&&p[i]<='9')n[ns++]=p[i]-'0';
	 else n[ns++]=find(begin,p[i]);
	 break;
}

if(p[i]=='#')break;
i++;
}
return n[0];
}


int main()
{char a[100],b[100];
	int t,i,j;
	cin>>t;cin.get();
	for(;t>0;t--)
	{for(j=0;;j++){a[j]=cin.get();if(a[j]==9||a[j]==32)j--;if(a[j]==10)break;}
		a[j]='#';a[j+1]=0;
	 for(j=0;;j++){b[j]=cin.get();if(b[j]==9||b[j]==32)j--;if(b[j]==10)break;}
	        b[j]='#';b[j+1]=0;

	for(i=0;i<10;i++)if(js(a,i,0)!=js(b,i,1))break;
//	cout<<i<<" "<<js(a,i,0)<<" "<<js(b,i,1)<<endl;
	if(i<10)cout<<"NO\n";
	else cout<<"YES\n";
	}
return 0;
}