这题考的是字符串处理，然而十分繁琐，需要一定的技巧，还要十分注重细节
###算法
二分法——不断地寻找当前优先级最低的运算符，然后以它为中心将算式分成两段递归计算。
带入求值——因为要用多项式乘法对算式进行展开计算的话，不仅程序冗长繁琐，而且程序执行效率也十分低下。由于OI比赛的题目只有十组测试点，而且是按点得分，所以我们可以考虑用具体数字带入a求表达式的值来判断。为了减少误差，必须多取几个值。
###细节问题
1. 如果带入整数，由于幂指数很高，所以有上溢的风险，必须加上取模，当然这是建立在对模算术熟悉的基础上。在这里笔者带入的是小浮点数，可以巧妙地避免溢出。
1. 带入小数就产生了如何比较两个小数相等的问题。小数大小不能用等号直接比较，这应该属于常识了。而常用的方法（比较差是否小于eps，eps一般去10的-6次到10的-9次不等），在这数量级悬殊的数字比较上也无能为力。所以我们可以先比较它们的数量级（log10的值）是否相同，再去比较值。然而这种方法实测时误差不小，请尽量少在别的题目中使用。
1. 题目中的表达式可能会出现多括号、少括号的情况，必须自己把括号补上。
1. 此题的读入也十分猥琐。由于空格的存在所以不能用scanf直接读取了，C++必须gets\fgets\getline，然后自己慢慢处理吧……
###标程1；
#include <cstdio>
#include <cstring>
#include <cmath>
double A; // 代表用来替代a的值
class expr
{
public:
char s[100],ts[100];
double getnum(int l,int r) // 获取数字
{
int i,x=0;
for (i=l;i<=r;i++)
x=x*10+(int)s[i]-48;
return (double)x;
}
double calc(int l,int r) // 计算从l到r的表达式的值
{
int i,k;
for (i=r,k=0;i>=l;i--) // 从优先级最低的加减号开始
{
if (k==0)
{
if (s[i]=='+')
return calc(l,i-1)+calc(i+1,r);
else if (s[i]=='-')
return calc(l,i-1)-calc(i+1,r);
}
if (s[i]=='(') k++;
else if (s[i]==')') k--;
}
for (i=r,k=0;i>=l;i--) // 处理乘号
{
if (k==0)
if (s[i]=='*')
return calc(l,i-1)*calc(i+1,r);
if (s[i]=='(') k++;
else if (s[i]==')') k--;
}
for (i=r,k=0;i>=l;i--) // 处理乘方
{
if (k==0)
if (s[i]=='^')
return pow(calc(l,i-1),calc(i+1,r));
if (s[i]=='(') k++;
else if (s[i]==')') k--;
}
if (s[l]=='('&&s[r]==')') // 处理括号
return calc(l+1,r-1);
if (l==r&&s[l]=='a') // 用A替代字母a的值
return A;
else
return getnum(l,r);
}
void scan() // 读入字符串并进行预处理
{
int i,j,k;
memset(ts,0,sizeof(ts));
memset(s,0,sizeof(s));
fgets(ts,sizeof(ts),stdin);
for (i=0,j=0,k=0;i<strlen(ts);i++)
if (ts[i]!=' '&&ts[i]!='\n') // 过滤空格和fgets读到的换行符
{
if (ts[i]=='('&&ts[i-1]==')') // 在两个相邻的括号之间添加乘号
s[j++]='*';
else if (ts[i]=='a'&&ts[i-1]>='0'&&ts[i-1]<='9') // 在a与它的系数之间添加乘号
s[j++]='*';
if (ts[i]=='(') k++;
else if (ts[i]==')') k--; // 统计括号数目
s[j++]=ts[i];
}
if (k>0) while (k--) s[j++]=')'; // 如果左括号多了，补充右括号
else if (k<0) // 如果有括号多了，补充左括号（这里用的方法很低效，应该还有更好的方案）
{
memset(ts,0,sizeof(ts)); j=0;
while (k++) ts[j++]='(';
strcat(ts,s);
memset(s,0,sizeof(s));
strcpy(s,ts);
}
}
double work() // 计算表达式的值
{
return calc(0,strlen(s)-1);
}
};
bool cmp(double a,double b) // 比较两个浮点数是否相等（这个方法误差其实很大）
{
int x,y;
double r;
x=(int)log10(a)+1;y=(int)log10(b)+1;
if (x!=y) return false;
r=pow(10,x-12);
if (fabs(a-b)>r) return false;
return true;
}
double P1,P2,P3,Q1,Q2,Q3;
int N,i;
expr S;
char ss[100];
int main()
{
S.scan();
A=0.7; P1=S.work();
A=1.4; P2=S.work();
A=2.1; P3=S.work();
fgets(ss,sizeof(ss),stdin);
sscanf(ss,"%d",&N); // 读入N
for (i=1;i<=N;i++)
{
S.scan();
A=0.7; Q1=S.work();
A=1.4; Q2=S.work();
A=2.1; Q3=S.work();
if (cmp(P1,Q1)&&cmp(P2,Q2)&&cmp(P3,Q3))
printf("%c",(char)(64+i));
}
}
2：
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
struct expr
{
char s[100],t[100];
int len;
double getnum(int l,int r)
{
int ret=0;
for(int i=l;i<=r;i++)
ret=ret*10+(s[i]-'0');
return(double)ret;
}
double calc(int A,int l,int r)
{
for(int k=0,i=r;i>=l;i--)
{
if(k==0)
{
if(s[i]=='+')
return calc(A,l,i-1)+calc(A,i+1,r);
if(s[i]=='-')
return calc(A,l,i-1)-calc(A,i+1,r);
}
if(s[i]==')')
k++;
if(s[i]=='(')
k--;
}
for(int k=0,i=r;i>=l;i--)
{
if(k==0&&s[i]=='*')
return calc(A,l,i-1)*calc(A,i+1,r);
if(s[i]==')')
k++;
if(s[i]=='(')
k--;
}
for(int k=0,i=r;i>=l;i--)
{
if(k==0&&s[i]=='^')
return pow(calc(A,l,i-1),calc(A,i+1,r));
if(s[i]==')')
k++;
if(s[i]=='(')
k--;
}
if(s[l]=='('&&s[r]==')')
return calc(A,l+1,r-1);
if(l==r&&s[l]=='a')
return A;
return getnum(l,r);
}
double work(int A)
{
return calc(A,0,len-1);
}
void scan()
{
memset(s,0,sizeof(s));
memset(t,0,sizeof(t));
len=0;
fgets(t,sizeof(t),stdin);
for(int i=0,l=strlen(t);i<l;i++)
if(t[i]!=' '&&t[i]!='\n')
s[len++]=t[i];
}
}S;
double P1=0.6450,P2=2.9970,P3=1.4250,A1,A2,A3,B1,B2,B3;
bool e(double x,double y)
{
int l1=(int)log10(x)+1,l2=(int)log10(y)+1;
if(l1!=l2)
return 0;
double r=pow(10.00,abs(l1)-10.00);
if(fabs(x-y)<r)
return 1;
return 0;
}
char in[100],ans[100];
int N,cnt=0;
main()
{
S.scan();
A1=S.work(P1);
A2=S.work(P2);
A3=S.work(P3);
fgets(in,sizeof(in),stdin);
sscanf(in,"%d",&N);
for(int i=0;i<N;i++)
{
S.scan();
B1=S.work(P1);
B2=S.work(P2);
B3=S.work(P3);
if(e(A1,B1)&&e(A2,B2)&&e(A3,B3))
ans[cnt++]='A'+i;
}
for(int i=0;i<cnt;i++)
printf("%c",ans[i]);
}
3：
此题直接整理多项式极为困难，且花费时间多。
可以取三个double的特殊值进行运算。
这三个特殊值必须取得有技巧，本人因为取得不好WA了8次……
代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
inline int abs(int x) { return (x > 0 ? x : -x); }
struct expr
{
char s[100] , t[100];
int len;
double getnum(int l , int r)
{
int ret = 0;
for (int i = l ; i <= r ; ++i)
ret = ret * 10 + (s[i] - '0');
return (double)ret;
}
double calc(int A , int l , int r)
{
for (int k = 0 , i = r ; i >= l ; --i)
{
if (k == 0)
{
if (s[i] == '+') return calc(A , l , i - 1) + calc(A , i + 1 , r);
if (s[i] == '-') return calc(A , l , i - 1) - calc(A , i + 1 , r);
}
if (s[i] == ')') ++k;
if (s[i] == '(') --k;
}
for (int k = 0 , i = r ; i >= l ; --i)
{
if (k == 0 && s[i] == '*')
return calc(A , l , i - 1) * calc(A , i + 1 , r);
if (s[i] == ')') ++k;
if (s[i] == '(') --k;
}
for (int k = 0 , i = r ; i >= l ; --i)
{
if (k == 0 && s[i] == '^')
return pow(calc(A , l , i - 1) , calc(A , i + 1 , r));
if (s[i] == ')') ++k;
if (s[i] == '(') --k;
}
if (s[l] == '(' && s[r] == ')')
return calc(A , l + 1 , r - 1);
if (l == r && s[l] == 'a')
return A;
return getnum(l , r);
}
double work(int A)
{
return calc(A , 0 , len - 1);
}
void scan()
{
memset(s , 0 , sizeof(s));
memset(t , 0 , sizeof(t));
len = 0;
fgets(t , sizeof(t) , stdin);
for (int i = 0 , l = strlen(t) ; i < l ; ++i)
if (t[i] != ' ' && t[i] != '\n')
s[len++] = t[i];
}
}S;
double P1 = 0.6450 , P2 = 2.9970 , P3 = 1.4250;
double A1 , A2 , A3;
double B1 , B2 , B3;
bool e(double x , double y)
{
int l1 = (int)log10(x) + 1 , l2 = (int)log10(y) + 1;
if (l1 != l2)
return false;
double r = pow(10.00 , abs(l1) - 10.00);
if (fabs(x - y) < r)
return true;
return false;
}
char in[100] , ans[100];
int N , cnt = 0;
int main()
{
S.scan();
A1 = S.work(P1);
A2 = S.work(P2);
A3 = S.work(P3);
fgets(in , sizeof(in) , stdin);
sscanf(in , "%d" , &N);
for (int i = 0 ; i < N ; ++i)
{
S.scan();
B1 = S.work(P1);
B2 = S.work(P2);
B3 = S.work(P3);
if (e(A1 , B1) && e(A2 , B2) && e(A3 , B3))
ans[cnt++] = 'A' + i;
}
for (int i = 0 ; i < cnt ; ++i)
printf("%c" , ans[i]);
printf("\n");
return 0;
}
评测结果
编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 828 KiB, score = 10
测试数据 #1: Accepted, time = 11 ms, mem = 832 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 828 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 832 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 828 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 832 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 832 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 832 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 828 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 832 KiB, score = 10
Accepted, time = 56 ms, mem = 832 KiB, score = 100

pivoefhiyg

program equal;
var
s:string;
h:array[1..100]of int64;
i,kk:longint;
ans:int64;
n,base,m,p:int64;
function power(x:int64;y:longint):int64;
var i:longint;
begin
x:=x mod maxlongint;
power:=1;
for i:=1 to y do
power:=power*x mod maxlongint;
end;
function data(l,r:longint):int64;
var i:longint;
begin
data:=0;
for i:=l to r do data:=data*10+ord(s[i])-48;
end;

function find(l,r:longint):int64;
var i,min:longint;
begin
min:=maxlongint;
find:=0;
for i:=r downto l do
if h[i]<min then
begin min:=h[i]; find:=i; end;
end;

function opt(a,k,b:int64):int64;
begin
case s[k] of
'+':opt:=(a+b) mod maxlongint;
'-':opt:=(a-b) mod maxlongint;
'*':opt:=(a*b) mod maxlongint;
'^':opt:=power(a,b) mod maxlongint
end;
end;

function work(L,r:longint):int64;
var a,b:int64;
k:longint;
begin
if s[l]='(' then inc(l);
if s[r]=')' then dec(r);
k:=find(l,r);
if k=0 then exit(data(l,r));
a:=work(l,k-1);
b:=work(k+1,r);
work:=opt(a,k,b);
end;
begin

readln(s);
p:=pos(' ',s);
while p<>0 do
begin
delete(s,p,1);
p:=pos(' ',s);
end;
n:=length(s);
for i:=1 to n do
if s[i]='a' then s[i]:='2';
for i:=1 to n do h[i]:=maxlongint;
base:=0;
for i:=1 to n do
case s[i] of
'(' : inc(base,3);
')' : dec(base,3);
'+','-' : h[i]:=base+1;
'*', '/': h[i]:=base+2;
'^' : h[i]:=base+3;
end;
ans:=work(1,n) mod maxlongint;
readln(m);
for kk:=1 to m do
begin
readln(s);
p:=pos(' ',s);
while p<>0 do
begin
delete(s,p,1);
p:=pos(' ',s);
end;
n:=length(s);
for i:=1 to n do
if s[i]='a' then s[i]:='2';
for i:=1 to n do h[i]:=maxlongint;
base:=0;
for i:=1 to n do
case s[i] of
'(' : inc(base,3);
')' : dec(base,3);
'+','-' : h[i]:=base+1;
'*' : h[i]:=base+2;
'^' : h[i]:=base+3;
end;
if ans=work(1,n) mod maxlongint then write(chr(64+kk));
end;
writeln;

end.

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 576 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 580 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 576 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 580 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 576 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 580 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 576 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 576 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 576 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 580 KiB, score = 10

Accepted, time = 30 ms, mem = 580 KiB, score = 100

在《C++程序设计语言》里看到过类似的程序，只不过那个只有加减号，但是这种递归的算法还是挺好扩展的

#include<iostream>
#include<cstdio>
#include<string>
#include<sstream>
using namespace std;
const char* alph = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
long long a;
long long stand[15];

long long jia(stringstream&);
long long cheng(stringstream&);

long long pow (long long a, long long b) {
    long long ans = 1;
    for (int i = 0; i < b; i++) ans *= a;
    return ans;
}

bool check () {
    string line; getline(cin, line);
    for (a = 0; a < 10; a++) {
        stringstream ss(line);
        if (jia(ss) != stand[a]) return false;
    }
    return true;
}

int main ()
{
    int n;
    string line; 
    getline(cin, line);
    for (a = 0; a < 10; a++) {
        stringstream ss(line);
        stand[a] = jia(ss);
    }
    cin >> n;
    getchar();
    for(int i = 0; i < n; i++) 
        if (check()) cout << alph[i];
    return 0;
}

long long pan(stringstream& ss) {
    long long num = 0;
    char c = 0;
    ss >> c;
    if (c == 'a') return (long long)a;
    else {
        ss.putback(c);
        ss >> num;
        return num;
    }
}

long long getnum(stringstream& ss) {
    long long b = 0;
    char c = 0;
    b = pan(ss);
    ss >> c;
    while (c == '^') {
        long long d;
        d = pan(ss);
        b = pow(b, d);
        c = 0;
        ss >> c;
    }
    ss.putback(c);
    return b;
}

long long cheng (stringstream& ss) {
    char c = 0;
    long long ans = 0;
    long long num = 0;
    ss >> c;
    if (c == '(') ans = jia(ss);
    else {
        ss.putback(c);
        ans = getnum(ss);
    } 
    while (ss >> c) {
        switch (c) {
            case ' ' :
                continue;
            case '*' :
                ss >> c;
                if (c == '(') num = jia(ss);
                else {
                    ss.putback(c);
                    num = getnum(ss);
                }
                ans *= num;
                break;
            default : 
                ss.putback(c); 
                return ans;
        }
    }
    return ans;
}

long long jia (stringstream& ss) {
    char c = 0;
    long long ans = 0;
    ans = cheng(ss);
    while (ss >> c) {
        switch (c) {
            case ' ' :
                continue;
            case '+' : 
                ans += cheng(ss);
                break; 
            case '-' :
                ans -= cheng(ss);
                break; 
            case ')' :
                ss >> c;
                while (c == '^') {
                    long long b;
                    b = pan(ss);
                    ans = pow(ans, b);
                    c = 0;
                    ss >> c;
                }
                ss.putback(c);
                return ans;
        }    
    }
    return ans; 
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[9999],fuhao[9999];
long long shuzi[9999],p1,p;
long long cal(char f)
{
switch(f)
{
case '#':return 0;
case '(':return 1;
case '+':
case '-':return 2;
case '*':
case '/':
case '%':return 3;
case '^':return 4;
}
}
long long jisuan(long long a,long long b,char c)
{
switch(c)
{
case '+':return a+b;
case '-':return a-b;
case '*':return a*b;
case '/':return a/b;
case '%':return a%b;
case '^':
{
long long t=1;
for(long long i=1;i<=b;i++)
t*=a;
return t;
}
}
}
void calculate()
{
long long a=shuzi[p1-1],b=shuzi[p1-2];p1-=2;
char c=fuhao[p-1];p--;
shuzi[p1++]=jisuan(b,a,c);
}
long long cxspc(long long k,char str[])
{
memset(shuzi,0,sizeof(shuzi));
memset(fuhao,0,sizeof(fuhao));
p1=0;p=0;
long long i=0;
fuhao[p++]='#';
while(1)
{
if(str[i]==0)break;
else if(str[i]==' '){i++;continue;}
else if(str[i]=='a'){shuzi[p1++]=k;i++;continue;}
else if(str[i]>='0'&&str[i]<='9')
{
long long t=0;
while(str[i]>='0'&&str[i]<='9')
t=t*10+str[i++]-'0';
shuzi[p1++]=t;
}
else if(str[i]=='+'&&(i==0||str[i-1]=='('))i++;
else if(str[i]=='-'&&(i==0||str[i-1]=='('))
{
shuzi[p1++]=0;
fuhao[p++]=str[i];
i++;
}
else
{
if(str[i]=='(')fuhao[p++]='(';
else if(str[i]==')')
{
while(fuhao[p-1]!='(')
calculate();
p--;
}
else if(cal(str[i])>cal(fuhao[p-1]))fuhao[p++]=str[i];
else{
while(cal(str[i])<=cal(fuhao[p-1]))
calculate();
fuhao[p++]=str[i];
}
i++;
}
}
while(p!=1)calculate();
return shuzi[0];
}
int main()
{
long long ans[11],n;
gets(str);
for(long long i=-5;i<=5;i++)
ans[i+5]=cxspc(i,str);
scanf("%d",&n);
getchar();
for(long long j=0;j<n;j++)
{
gets(str);
long long pd=0;
for(long long i=-5;i<=5;i++)
{
long long xx=cxspc(i,str);
if(xx!=ans[i+5])
{pd=1;break;}
}
if(pd==0)
cout<<(char)('A'+j);
}
return 0;
}

用两个栈来做
对于a就特殊处理一下
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
typedef bool boolean;
stack<char> op;
stack<long long> num;
int n;
boolean can(char oper){
if(op.empty()) return false;
if(oper=='(') return false;
if(oper==')') return true;
char cf=op.top();
if(cf=='(') return false;
if(cf==oper) return true;
if(cf==')') return true;
if(cf=='^'&&oper!=')') return true;
if(cf=='*'&&(oper=='+'||oper=='-')) return true;
if(cf=='+'&&oper=='-') return true;
if(cf=='-'&&oper=='+') return true;
return false;
}
long long pow(long long n,short int pos){
if(pos==1) return n;
if(pos%2==1) return pow(n,pos/2)*pow(n,pos/2)*n;
return pow(n,pos/2)*pow(n,pos/2);
}
long long cale(char oper){
long long result = 0;
long long b = num.top();
num.pop();
long long a = num.top();
num.pop();
switch(oper){
case '+':
result=a+b;
break;
case '-':
result=a-b;
break;
case '*':
result=a*b;
break;
case '^':
result=pow(a,b);
break;
}
op.pop();
return result;
}
long long getResult(string str){
int index=0;
while(index<str.length()){
if(str[index]==' '){
index++;
continue;
}
if(index<str.length()&&str[index]>='0'&&str[index]<='9'){
int math = 0;
while(index<str.length()&&str[index]>='0'&&str[index]<='9'){
math*=10;
math+=str[index]-'0';
index++;
}
num.push(math);
continue;
}
if(index<str.length()&&str[index]=='a'){
num.push(-10001);
index++;
continue;
}
while(index<str.length()&&(!op.empty())&&can(str[index])){
if(str[index]==')'){
while(op.top()!='(')
num.push(cale(op.top()));
op.pop();
break;
}else{
num.push(cale(op.top()));
}
}
if(str[index]!=')')
op.push(str[index]);
index++;
}
while(!op.empty()){
num.push(cale(op.top()));
}
long long result=num.top();
num.pop();
return result;
}
string s;
long long answer;
int main(){
getline(cin,s);
answer=getResult(s);
cin>>n;
getline(cin,s);
for(int i=1;i<=n;i++){
getline(cin,s);
if(getResult(s)==answer) cout<<(char)('A'+i-1);
}
return 0;
}

我的题解

有木有用二叉树表达的呢？

求代码。。。。。。。

···C++

int build_tree(string s,int x,int y)

{

int i=1,c1=-1,c2=-1,c3=-1,p=0;

int u;

if(y-x==1)

{

u=++nc;

lch[u]=0;rch[u]=0;op[u]=s[x];

return u;

}

for(i=x;i<y;i++)

{

switch(s[i])

{

case'(':p++;break;

case')':p--;break;

case'+':case'-':if(!p) c1=i;break;

case'*':if(!p) c2=i;break;

case'^':if(!p) c3=i;break;

}

}
// system("pause");
if(c1<0) c1=c2;

if(c1<0) c1=c3;

if(c1<0) return build_tree(s,x+1,y-1);

u=++nc;

lch[u]=build_tree(s,x,c1);

rch[u]=build_tree(s,c1+1,y);

op[u]=s[c1];

return u;

}

···

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;

char jibie[10][10]={{'0','0','0','0','0','0','0','0','0'},
{'0','<','<','<','<','<','>','0','>'},
{'0','<','<','<','<','<','>','0','>'},
{'0','>','>','<','<','<','>','0','>'},
{'0','>','>','<','<','<','>','0','>'},
{'0','>','>','>','>','<','>','0','>'},
{'0','>','>','>','>','>','>','=','>'},
{'0','<','<','<','<','<','=','0','0'},
{'0','<','<','<','<','<','<','<','0'}};
char opr[100];
int opd[100],topr,topd;
const int M=10007;
int cc(int x,char ch,int y)
{
int z;
switch(ch)
{
case '+':z=(x+y)%M;break;
case '-':z=(x-y)%M;break;
case '*':z=(x*y)%M;break;
case '/':z=x/y;break;
case '^':if(x==0)return 0;
else{
z=1;
for(int i=1;i<=y;i++)
z=(z*x)%M;
break;}
}
return z;
}
char findjibie(char s,char t)
{
int x,y;
switch(s)
{
case '+':x=1;break;
case '-':x=2;break;
case '*':x=3;break;
case '/':x=4;break;
case '^':x=5;break;
case '(':x=6;break;
case ')':x=7;break;
case '#':x=8;break;
}
switch(t)
{
case '+':y=1;break;
case '-':y=2;break;
case '*':y=3;break;
case '/':y=4;break;
case '^':y=5;break;
case '(':y=6;break;
case ')':y=7;break;
case '#':y=8;break;
}
return jibie[x][y];
}
int count(int data,char s[100])
{
opr[1]='#';topr=1;topd=0;
int i=0;
int flag=0,d=0;
while(!(s[i]=='#'&&opr[topr]=='#'))
{
if(s[i]>='0'&&s[i]<='9')
{
if(!flag){opd[++topd]=s[i]-'0';flag=1;}
else{d=opd[topd--];d=d*10+s[i]-'0';opd[++topd]=d;}
i++;
}
else
if(s[i]==' '){flag=0;i++;}
else
if(s[i]=='a'){opd[++topd]=data;flag=0;i++;}
else
{
flag=0;
char tch=findjibie(s[i],opr[topr]);
int x,y,zt;
char ttch;
switch(tch)
{
case '>':opr[++topr]=s[i];i++;break;
case '<':y=opd[topd--];
x=opd[topd--];
ttch=opr[topr--];
zt=cc(x,ttch,y);
opd[++topd]=zt;
break;
case '=':topr--;i++;break;
}
}
}
return opd[1];
}
int st[6],ts[27],n,flagg[27];
int main()
{
//freopen("equal9.in","r",stdin);
char tmp[100],t[27][100];
gets(tmp);
tmp[strlen(tmp)]='#';
cin>>n;
char aa;
scanf("%c",&aa);
for(int i=1;i<=n;i++)
{
gets(t[i]);
t[i][strlen(t[i])]='#';
}
for(int i=1;i<=5;i++)
st[i]=count(i,tmp);
for(int i=1;i<=5;i++)
{
for(int j=1;j<=n;j++)
{
int x=count(i,t[j]);
if(x!=st[i])flagg[j]=1;
}
}
for(int i=1;i<=n;i++)
if(!flagg[i])printf("%c",'A'+i-1);
return 0;
}
希望你们看得懂..........

我有本题的测试数据 ， 需要Q我 812483101
本题有几个细节注意 ， 见代码
//
// main.cpp
// cvs1107+
//
// Created by Fuxey on 15/10/26.
// Copyright © 2015年 corn.crimsonresearch. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <sstream>

using namespace std;
const int maxn = 30;
typedef unsigned long long ull;

string s[maxn];
int n;
bool ok[maxn];
const ull text[]={1,17,103,1007,23,29,31};

int id(char c) { if(c==')') return 0; if(c=='+') return 1; if(c=='-') return 2; if(c=='*') return 3; if(c=='^') return 4; return 5;}
int pri[6] = {0,1,1,2,3,4};

ull pows(ull a , ull b)
{
if(b==1) return a;
ull res = pows(a, b/2);
if(b%2) return res*res*a;
return res*res;
}

ull cal(ull a , ull b , int c)
{
if(c==1) return a+b;
if(c==2) return a-b;
if(c==3) return a*b;
if(c==4) return pows(a, b);
return 0;
}

ull getValue(int k , ull a)
{
stack<int> op;
stack<ull> numbers;
for(int i=0;i<s[k].size();i++) if(s[k][i]!=' ')
{
if(isdigit(s[k][i]) || s[k][i]=='a')
{
if(s[k][i]=='a') { numbers.push(a); continue; }
int now = 0 , j;
for(j=i;j<s[k].size() && isdigit(s[k][j]); j++) now = now*10+(int)(s[k][j]-'0');
numbers.push(now);
i = j-1;
}
else
{
if(op.size() && op.top()==5 && s[k][i]==')') { op.pop(); }
else if(op.size()==0 || pri[op.top()]<pri[id(s[k][i])] || op.top()==5) op.push(id(s[k][i]));
else
{
while(op.size() && pri[op.top()]>=pri[id(s[k][i])])
{
if(s[k][i]!=')' && op.top()==5) break;
int c = op.top(); op.pop();
if(pri[c]==4 && pri[id(s[k][i])]==0) break;
if(numbers.size()==1) break;
ull b = numbers.top(); numbers.pop();
ull a = numbers.top(); numbers.pop();
numbers.push(cal(a, b, c));
}
if(s[k][i]!=')') op.push(id(s[k][i]));
}
}
}
return numbers.top();
}

int main(int argc, const char * argv[]) {

getline(cin, s[0]);
s[0] = s[0]+')';
cin>>n; getline(cin, s[1]);
for(int i=1;i<=n;i++) { getline(cin, s[i]); s[i] = s[i]+')'; }

for(int i=1;i<=n;i++) ok[i] = true;
for(int i=0;i<7;i++)
{
ull num = getValue(0 , text[i]);
for(int j=1;j<=n;j++) if(getValue(j, text[i])!=num) ok[j] = false;
}

for(int i=1;i<=n;i++) if(ok[i]) cout<<((char)('A'+i-1));
cout<<endl;
return 0;
}

原来没过的人也可以发题解

不需要考虑括号不匹配问题，输入绝对合法。不需要考虑形如
（-3+a^7）*2
这样的情况。
另一方面，我认为只有试够11个数才能充分说明正确性：因为
a^10+k9*a^9+k8*a^8+.......=(a+3)^10+......
这是一个一元十次方程，它需要11个点来确定一条十次曲线。所以要将0-10都代入才能说明问题。
当然，如果这是一条6次曲线，7个点就够，可是谁有想写一个判断次数的函数呢？

因为取余运算，导致运算顺序不同，结果就不同。这是一个神坑。所以试的点少一点，取余数大一点就容易过。

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <vector>
#include <cstdio>
#include <string>
#include<string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define exp 1e-8
#define INF 100000000
#define ll long long
#define set(a,b) memset(a,b,sizeof(a));
void bug(string st="bug")
{cout<<st<<endl;}
ll pow(ll a,int b)
{
ll sum=1;
while(b--)
{
sum*=a;
}
return sum;
}
ll doit(char temp[],int a,int s,int t,int &id)
{
stack<ll>sta1;
while(s<=t&&temp[s]!=')')
{
//cout<<s<<" ";
ll sum=0;
char ch=temp[s];
if(ch=='*'||ch=='+'||ch=='-')
s++;
int p;
if(temp[s]=='(')
sum=doit(temp,a,s+1,t,p),s=p+1;
else if((temp[s]>='0'&&temp[s]<='9')||temp[s]=='a')
{
for(int &i=s;s<=t&&((temp[i]>='0'&&temp[i]<='9')||temp[i]=='a');i++)
{
if(temp[i]!='a')
sum=sum*10+temp[i]-'0';
else
sum=sum*10+a;
}
}
while(s<=t&&temp[s]=='^')
{
s++;
int e=0;
for(int &i=s;s<=t&&((temp[i]>='0'&&temp[i]<='9')||temp[i]=='a');i++)
{
if(temp[i]!='a')
e=e*10+temp[i]-'0';
else
e=e*10+a;
}
sum=pow(sum,e);
}
//cout<<s<<" "<<ch<<" "<<sum<<endl;
if(ch=='*')
{
ll temp=sta1.top();
sta1.pop();
temp*=sum;
sta1.push(temp);
}
else if(ch=='+'||(ch>='0'&&ch<='9')||ch=='a'||ch=='(')
sta1.push(sum);
else if(ch=='-')
sta1.push(-sum);
}
id=s;
ll ans=0;
while(!sta1.empty())
{
ans+=sta1.top();
sta1.pop();
}
return ans;
}
int main()
{
char k[60],ch;
int idx=1;
while((ch=getchar())!='\n')
{
if(ch==' ')
continue;
k[idx++]=ch;
}
k[0]='(',k[idx]=')';
//for(int i=0;i<=idx;i++)
// cout<<k[i];
// cout<<endl;
ll num[10];
int id=idx;
for(int i=1;i<10;i++)
{
num[i]=doit(k,i,1,idx,id);
//cout<<num[i]<<endl;
}
int cnt;
cin>>cnt;
getchar();
char ansch[40];
int anscnt=0;
for(int cas=0;cas<cnt;cas++)
{
idx=1;
char ktemp[60];
while(ch=getchar())
{
if(ch=='\n')break;
if(ch==' ')
continue;
ktemp[idx++]=ch;
}
ktemp[0]='+',ktemp[idx]=')';
bool ok=1;
for(int i=1;i<10;i++)
{
if(num[i]!=doit(ktemp,i,1,idx,id))
ok=0;
//cout<<num[i]<<" "<<doit(ktemp,i,1,idx,id)<<endl;
}
if(ok==1)
ansch[anscnt++]=char('A'+cas);
}
for(int i=0;i<anscnt;i++)
cout<<ansch[i];
return 0;
}

program bdsqz;
var s:string;
fuhao:array[1..100] of char;
shuzhi:Array[1..100] of longint;
l1,l2,i,j,l,k,t:longint;
c:char;
function jibie(c:char):integer;
begin
case c of
'+','-':exit(1);
'*','/':exit(3);
'^':exit(5);
'(':exit(0);
end;
end;
function jisuan(x,y:longint;c:char):longint;
var r:longint;
begin
case c of
'+':exit(x+y);
'-':exit(x-y);
'*':exit(x*y);
'/':exit(x div y);
'^':begin
jisuan:=1;
for r:=1 to y do
jisuan:=jisuan*x;
end;
end;
end;
begin
readln(s);
read(t);
l:=length(s);
i:=1;
while i<=l do
begin
if s[i] in['+','-','*','/','^'] then
begin
if (l1<>0)and(jibie(s[i])<=jibie(fuhao[l1]))then
begin
k:=jisuan(shuzhi[l2-1],shuzhi[l2],fuhao[l1]);
dec(l1);dec(l2);
shuzhi[l2]:=k;
end;
inc(l1);fuhao[l1]:=s[i];
end;
if s[i]='(' then begin inc(l1);fuhao[l1]:=s[i];end;
if s[i]=')' then
begin
while fuhao[l1]<>'(' do
begin
k:=jisuan(shuzhi[l2-1],shuzhi[l2],fuhao[l1]);
dec(l1);dec(l2);
shuzhi[l2]:=k;
end;
dec(l1);
end;
if s[i]='a' then begin inc(l2);shuzhi[l2]:=t;end;
if s[i] in['0'..'9'] then
begin
k:=ord(s[i])-48;inc(i);
while s[i] in ['0'..'9'] do
begin
k:=k*10+ord(s[i])-48;
inc(i);
end;
inc(l2);
shuzhi[l2]:=k;
dec(i);
end;
inc(i);
end;
while l1>0 do
begin
k:=jisuan(shuzhi[l2-1],shuzhi[l2],fuhao[l1]);
dec(l1);dec(l2);
shuzhi[l2]:=k;
end;
writeln(shuzhi[l2]);

end.

###inline Code
Here is the answer.
###Block code
#include<cstdio>
#include<cstring>
#include<cctype>
#include<string>
#include<stack>
#include<cmath>
#include<iostream>
#define oo 2147483647
using namespace std;
long long power(long long a, long long b)
{
long long ans = 1;
for(int i = 0; i < b; i++)
ans = (ans*a);
return ans;
}
bool can(char top, char ss)
{
bool flag = true;
switch(top)
{
case '+':
case '-':
switch(ss)
{
case '*':
case '^':
flag = false;
break;
}
case '*':
switch(ss)
{
case '^':
flag = false;
break;
}
break;
}
return flag;
}

string turn(string dan)
{
string gan;
// stack<char> temp;
int top=0;
char temp[257];
for(int i = 0; i < dan.size(); i++)
{
if(dan[i] == ' ')
continue;
if(dan[i] == '(')
// temp.push(dan[i]);
temp[++top]=dan[i];
else if(dan[i] == ')')
{
// while(!temp.empty() && temp.top() != '(')
while(top>0&&temp[top]!='(')
{
// gan += temp.top();
gan += temp[top];
// temp.pop();
top--;
}
// temp.pop();
top--;
}
else if(dan[i] == '+' || dan[i] == '-' || dan[i] == '*' || dan[i] == '^')
{
// while(!temp.empty())
while(top>0)
{
// if(temp.top()=='('||!can(temp.top(),dan[i]))
if(temp[top]=='('||!can(temp[top],dan[i]))
break;
gan += temp[top];
// gan += temp.top();
// temp.pop();
top--;
}
// temp.push(dan[i]);
temp[++top]=dan[i];
}
else
{
if(dan[i]>='0' && dan[i] <='9')
{
while(i < dan.size() && dan[i]>='0' &&dan[i]<='9')
{
gan += dan[i];
i++;
}
i--;
gan += "#";
}
else
gan += dan[i];
}
}
// while(!temp.empty())
while(top>0)
{
// gan += temp.top();
gan += temp[top];
// temp.pop();
top--;
}
return gan;
}
long long rand_me(string gan, int num)
{
int len = gan.length();
stack<long long> ans;
for(int i = 0; i < len; i++)
{
if(gan[i] == 'a')
ans.push(num);
else if(isdigit(gan[i]))
{
long long tmp = 0;
while(i < len && gan[i]>='0' && gan[i]<='9')
{
tmp = tmp*10 + (gan[i] - '0');
i++;
}
i--;
ans.push(tmp);
}
else if(gan[i] == '+')
{
long long tmp1 = ans.top();
ans.pop();
long long tmp2 = ans.top();
ans.pop();
ans.push((tmp1 + tmp2)%oo);
}
else if(gan[i] == '-')
{
long long tmp1 = ans.top();
ans.pop();
long long tmp2 = ans.top();
ans.pop();
ans.push(tmp2 - tmp1);
}
else if(gan[i] == '*')
{
long long tmp1 = ans.top();
ans.pop();
long long tmp2 = ans.top();
ans.pop();
ans.push((tmp1%oo * tmp2)%oo);
}
else if(gan[i] == '^')
{
long long tmp1 = ans.top();
ans.pop();
long long tmp2 = ans.top();
ans.pop();
ans.push(power(tmp2, tmp1)%oo);
}
}
return ans.top();
}
int main()
{
#ifndef DEBUG
freopen("equal.in","r",stdin);
freopen("equal.out","w",stdout);
#endif
string dan;
string gan;
getline(cin, dan);
gan = turn(dan);
string ss;
int n;
cin >> n;
getchar();
for(int i=0;i<n;i++)
{
getline(cin,ss);
string output = turn(ss);
int j;
for(j=0;j<=10;j++)
{
long long temp1 = rand_me(gan, j);
long long temp2 = rand_me(output, j);
// printf("temp1:%d temp2:%d\n",temp1,temp2);
if(temp1 != temp2)
break;
}
if(j > 10)
printf("%c", 'A'+i);
// printf("---------------------------------------------------------------\n");
}
printf("\n");
return 0;
}

C的题解！

取余数防止溢出，此方法不需要必须用35111,数据类型用int即可！

#include<stdio.h>
#include<string.h>
#include<math.h>
#define mod 25641

typedef struct
{
int str[100];
int top;
}shu;

typedef struct
{
char str[100];
int top;
}fu;

int youxian(char c,int a); /////1 为栈内，0为栈外！

int calculate(int a,char *p,int len);

int ret(char c,int a,int b);

int main()
{
int check[3]={3,7,13};
int timu[3];

int i,num,len,i_hh = 0;
char string[100];
char answer,hh[100];
gets(string);
scanf("%d",&num);
getchar();
len = strlen(string);
for(i = 0;i < 3;i++)
{
timu[i] = calculate(check[i],string,len);
//printf("%d\n",timu[i]);
}
for(i = 0,answer = 'A';i < num;i++,answer++)
{
int j,len;
int flag = 1;
char choice[100];
gets(choice);
len = strlen(choice);
for(j = 0;j < 3;j++)
{
//printf("%d\n",calculate(check[j],choice,len));
if(timu[j]!=calculate(check[j],choice,len))
{
flag = 0;
break;
}
}
if(flag)
hh[i_hh++] = answer;
}
for(i = 0;i < i_hh;i++)
printf("%c",hh[i]);
return 0;
}

int youxian(char c,int a)
{
int ret;
if(a) /////栈内，高
switch(c)
{
case '+':
case '-':ret = 2;break;
case '*':ret = 4;break;
case '^':ret = 6;break;
case '(':ret = 0;break;
case ')':ret = 8;break;
default:break;
}
else /////栈外
switch(c)
{
case '+':
case '-':ret = 1;break;
case '*':ret = 3;break;
case '^':ret = 5;break;
case '(':ret = 8;break;
case ')':ret = 0;break;
default:break;
}
if(c=='#')
ret = -1;
return ret;
}

int calculate(int a,char *p,int len)
{
shu number;
fu c;
int i;
int in = 1,out = 0;
number.top = -1;
c.top = 0;
c.str[0] = '#';
{
int l = 0,r = 0;
for(i = 0;i < len;i++)
{
if(p[i]=='(')
l++;
if(p[i]==')')
if(l)
l--;
else
p[i] = ' ';
}
}
for(i = 0;i < len;i++)
{
if(p[i]==' ')
continue;
else
if(p[i]=='a')
{
number.str[++number.top] = a;
}
else
if(p[i]>='0'&&p[i]<='9')
{
int temp = p[i] - '0';
i++;
while(p[i]>='0'&&p[i]<='9'&&i<len)
{
temp = temp*10+(p[i]-'0');
i++;
}
i--;
number.str[++number.top] = temp;
}
else //////////////////////优先级
{
if(youxian(p[i],out)>youxian(c.str[c.top],in))
c.str[++c.top] = p[i];
else
if(youxian(p[i],out)==youxian(c.str[c.top],in))
{
c.top--;
}
else
{
while(youxian(p[i],out)<youxian(c.str[c.top],in))
{
int a,b;
b = number.str[number.top--];
a = number.str[number.top--];
number.str[++number.top] = ret(c.str[c.top],a,b);
c.top--;
}
if(youxian(p[i],out)>youxian(c.str[c.top],in))
c.str[++c.top] = p[i];
else
{
c.top--;
}
}
}
}
while(c.top>0&&c.str[c.top]!='('&&c.str[c.top]!=')')
{
int a,b;
b = number.str[number.top--];
a = number.str[number.top--];
number.str[++number.top] = ret(c.str[c.top],a,b);
c.top--;
}
return (number.str[0]+25641); ///////////////////////此处很关键！！！！！！！！！！！！
}

int ret(char c,int a,int b)
{
int temp = 1;
switch(c)
{
case '+':
{
temp = a + b;
break;
}
case '-':
{
temp = a - b;
break;
}
case '*':
{
temp = a * b;
break;
}
case '^':
{
int i;
for(i = 0;i < b;i++)
{
temp*=a;
temp%=mod;
}
}
default:break;
}
return (temp+25641)%mod;/////////////////////////此处很关键！！！！！！！！！
}

终于AC了，发现用C的人好少。。。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <stack>
#include <vector>
#define p 1000007
using namespace std;
const char b[27]={'0','A','B','C','D','E','F','G',
'H','I','J','K','L','M','N','O',
'P','Q','R','S','T','U','V','W',
'X','Y','Z'};
string ss;
long long n,aim;
stack <char> ope;

long long strnum(string s)

{
long long num;
stringstream ss(s);
ss>>num;
return num;
}

int pre(char a)
{
if(a=='='||a=='(')return 0;
if(a=='+'||a=='-')return 1;
if(a=='*')return 2;
if(a=='^')return 3;
}
long long sta[555555],top;
long long work(string s)
{
string ss;
ss="";
memset(sta,0,sizeof(sta));top=0;
for(int i=0;i<s.size();i++)
{
if(s[i]>='0'&&s[i]<='9')
ss+=s[i];
else
{

if(s[i]==' ')
{
top++;
sta[top]=strnum(ss)%p;
ss="";

}

else
{
if(s[i]=='-')
{
long long s1,s2;
s2=sta[top];
if(top>0)
{top--;
s1=sta[top];
s1=s1-s2;
sta[top]=s1;}
continue;
}
if(s[i]=='+')
{
long long s1,s2;
s2=sta[top];
if(top>0)
{top--;
s1=sta[top];
s1=s1+s2;
sta[top]=s1;}
continue;

}
if(s[i]=='*')
{
long long s1,s2;
s1=sta[top];if(top>0) top--;
s2=sta[top];
s1=s1*s2;
sta[top]=s1;

continue;
}
if(s[i]=='^')
{
long long s1,s2;
s1=sta[top];if(top>0) top--;
s2=sta[top];
long long z=1LL;
for(int i=1;i<=s1;i++)
z=z*s2;
sta[top]=z;
continue;
}
}
}

}if(top==0)return strnum(ss);
else return sta[top];
}

string change(string str)
{
while(!ope.empty())

ope.pop();
string s;
s.clear();

ope.push('=');

int len = str.length();

for(int i = 0 ; i < len; ++i)

{

if(str[i] >= '0' && str[i] <= '9') s+=str[i];

else
{
if(str[i-1] >= '0' && str[i-1] <= '9')s+=' ';

if(str[i] == '(')
ope.push(str[i]);

else if(str[i] == ')')
{

while (ope.top() != '(')

{

s+=ope.top();

ope.pop();

}

ope.pop();

}

else if(pre(str[i]) > pre(ope.top())) ope.push(str[i]);

else

{

while(pre(str[i]) <= pre(ope.top()))
{

s+=ope.top();

ope.pop();

}

ope.push(str[i]);

}
}

}

while(ope.top() != '=')

{

if(s[s.size()-1]>= '0' && s[s.size()-1]<= '9')s+=' ';
s+=ope.top();

ope.pop();

}

return s;
}

int main()
{
string sss;
getline(cin,sss);
for(int i=0;i<sss.size();i++)
if(sss[i]!=' ')ss+=sss[i];
cin>>n;getchar();
for(int i=0;i<ss.size();i++)
if(ss[i]=='a')ss[i]='3';
long long aim=work(change(ss));
for(int i=1;i<=n;i++)
{
string s,s2;
getline(cin,s2);
for(int j=0;j<s2.size();j++)
if(s2[j]!=' ')s+=s2[j];
for(int j=0;j<s.size();j++)
if(s[j]=='a')s[j]='3';
long long z=work(change(s));
if(aim==z)cout<<b[i];
}cout<<endl;
return 0;
}

三次CE，一次WA 555555……再也不做这种题目了……

测试数据 #0: Accepted, time = 0 ms, mem = 748 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 748 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 748 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 748 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 748 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 748 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 752 KiB, score = 10
Accepted, time = 0 ms, mem = 752 KiB, score = 100