等价表达式 题解

个人觉得出题者的本意应该是要大家打分治或者栈判断表达式系数是否相等从而判断是否等价

本题解提供的做法是随机算法+表达式求值

通过多次随机出多个a值每次对给定的表达式求值若值不想等则表达式不等价，由于里面次方数过大又懒得打高精度 就把表达式的值对一个大质数取模（比如1e9+7）
（随机1000也不会超时吧，一般第一个值就把所有都排除了，很多人都是直接弄一个小质数就过了233）如果脸特别黑最后错了的话 就老实的去打正解分治吧（这得有多脸黑）
至于表达式求值就通过两个栈（数字栈和符号栈）以及符号运算优先级模拟实现（不会的自行参考代码学习）
等我哪天无聊再去打分治或者栈的做法的打法吧233

AC代码

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <queue>
#include <time.h>
using namespace std;
long long a[55],b[55],c[55];
int i,j,k,l,m,n,ha,hb,hx,hy,t,x,y;
char sd[30][55],s[55];
long long Mod=1e9+7;
long long num(long long tt,long long yy)
  {
    long long ll;
  	for (ll=1;yy;yy--) 
	  ll*=tt,ll%=Mod;
  	return ll;
  }
long long work(int x,int k)
  {
  	int n,i,j,l;
    for (l=strlen(sd[k]);l>=0;l--) s[l]=sd[k][l];
    l=strlen(sd[k]);
  	ha=hb=0;
  	memset(a,0,sizeof(a));memset(b,0,sizeof(b));
  	for (i=0;i<l;)
  	  {
  	  	if (s[i]=='a') b[++hb]=x;
  	  	if (s[i]=='(') a[++ha]=0;
  	  	if (s[i]==')') 
  	  	  {
  	  	  	for(;a[ha]!=0;)
  	  	  	  {
  	  	  	  	if (a[ha]==4) b[hb-1]=num(b[hb-1],b[hb])%Mod,hb--;
  	  	  	  	if (a[ha]==3) b[hb-1]=(b[hb-1]*b[hb])%Mod,hb--;
  	  	  	    if (a[ha]==2) b[hb-1]=(b[hb-1]-b[hb])%Mod,hb--;
  	  	  	    if (a[ha]==1) b[hb-1]=(b[hb-1]+b[hb])%Mod,hb--;
  	  	  	    ha--;
  	  	  	  }
  	  	  	ha--;
  	  	  }
  	  	if (s[i]=='*'||s[i]=='-'||s[i]=='+'||s[i]=='^')
  	  	{
  	  	if (s[i]=='^') n=4;
  	  	if (s[i]=='*') n=3;
  	  	if (s[i]=='-') n=2;
  	  	if (s[i]=='+') n=1;
  	  
  	  	for (;n<=a[ha];) 
  	  	  {
  	  	  	if (a[ha]==4) b[hb-1]=num(b[hb-1],b[hb])%Mod,hb--;
  	  	  	if (a[ha]==3) b[hb-1]=(b[hb-1]*b[hb])%Mod,hb--;
  	  	  	if (a[ha]==2) b[hb-1]=(b[hb-1]-b[hb])%Mod,hb--;
  	  	  	if (a[ha]==1) b[hb-1]=(b[hb-1]+b[hb])%Mod,hb--;
  	  	  	ha--;
  	  	  }
  	  	ha++;a[ha]=n;
  	    }
  	    if (s[i]>='0'&&s[i]<='9')
  	      {
  	      	t=0;
  	      	for (;s[i]>='0'&&s[i]<='9';i++) t=t*10+s[i]-'0';
			i--;b[++hb]=t; 
		  }
  	  	i++;
  	  }
  	for(;a[ha]!=0;)
  	   {
  	  	  	if (a[ha]==4) b[hb-1]=num(b[hb-1],b[hb])%Mod,hb--;
  	  	  	if (a[ha]==3) b[hb-1]=(b[hb-1]*b[hb])%Mod,hb--;
  	  	  	if (a[ha]==2) b[hb-1]=(b[hb-1]-b[hb])%Mod,hb--;
  	  	  	if (a[ha]==1) b[hb-1]=(b[hb-1]+b[hb])%Mod,hb--;
  	  	  	ha--;
  	   }
  	if (b[1]>=0) return (b[1]);else return(b[1]+Mod);
  }
int main()
  {
  	gets(sd[0]);
  	scanf("%d\n",&n);
	for (i=1;i<=n;i++) gets(sd[i]);
	for (i=1;i<=20;i++)
	  {
	  	x= rand() % 10000;
	  	y=work(x,0);
	  	for (j=1;j<=n;j++)
	  	  if (!c[j]) if (work(x,j)!=y) c[j]=1;
	  }
	for (i=1;i<=n;i++)
	  if (!c[i]) printf("%c",i+'A'-1);
  }

欢迎加入团队