code(RE但是已知数据都可以通过):
#include<iostream>
#include<vector>
#include<sstream>
#include<cmath>
#include<unordered_map>
#include<stack>
using namespace std;
struct node {
string val;
node* l;
node* r;
node(string x):val(x),l(nullptr),r(nullptr){}
};
string change(string s) {
string ret;
for(auto i:s)
if(i!=' ')ret+=i;
return ret;
}
double apply(double a,double b,char op) {
switch(op) {
case '+':return a+b;
case '-':return a-b;
case '*':return a*b;
case '^':return pow(a,b);
default:return 0;
}
}
node* to_tree(string infix) {
stack<node*> nodes;
stack<char> ops;
unordered_map<char,int> prec={{'+',1},{'-',1},{'*',2},{'^',3}};
string num;
for(int i=0;i<infix.size();i++) {
char c=infix[i];
if(isdigit(c)||c=='.')num+=c;
else if(c=='a')num+='a';
else {
if(!num.empty()) {
nodes.push(new node(num));
num.clear();
}
if(c=='(')ops.push(c);
else if(c==')') {
while(!ops.empty()&&ops.top()!='(') {
node* r=nodes.top();
nodes.pop();
node* l=nodes.top();
nodes.pop();
node* op=new node(string(1,ops.top()));
ops.pop();
op->l=l;
op->r=r;
nodes.push(op);
}
ops.pop();
}else {
while(!ops.empty()&&prec[ops.top()]>=prec[c]) {
node* r=nodes.top();
nodes.pop();
node* l=nodes.top();
nodes.pop();
node* op=new node(string(1,ops.top()));
ops.pop();
op->l=l;
op->r=r;
nodes.push(op);
}
ops.push(c);
}
}
}
if(!num.empty())
nodes.push(new node(num));
while(!ops.empty()) {
node* r=nodes.top();
nodes.pop();
node* l=nodes.top();
nodes.pop();
node* op=new node(string(1,ops.top()));
ops.pop();
op->l=l;
op->r=r;
nodes.push(op);
}
return nodes.top();
}
double eval(node* rt,int a) {
if(rt==NULL)return 0;
if(rt->val=="a")return a;
if(rt->val.length()>0&&(isdigit(rt->val[0])||(rt->val[0]=='-'&&isdigit(rt->val[1]))))return stod(rt->val);
else {
double l=eval(rt->l,a);
double r=eval(rt->r,a);
return apply(l,r,rt->val[0]);
}
}
void free_tree(node* rt) {
if(rt==nullptr)return ;
free_tree(rt->l);
free_tree(rt->r);
delete rt;
}
int main() {
string expr;
getline(cin,expr);
expr=change(expr);
int n;
cin>>n;
cin.ignore();
vector<string> option(n);
for(int i=0;i<n;i++) {
getline(cin,option[i]);
option[i]=change(option[i]);
}
string ans;
for(char i='A';i<'A'+n;i++) {
bool flag=true;
for(int a=0;a<=10;a++) {
node* rt1=to_tree(expr);
node* rt2=to_tree(option[i-'A']);
double x=eval(rt1,a);
double y=eval(rt2,a);
free_tree(rt1);
free_tree(rt2);
if(abs(x-y)>1e-9) {
flag=false;
break;
}
}
if(flag)ans+=i;
}
cout<<ans<<endl;
return 0;
}