RE求调
查看原帖
RE求调
1312687
luogu_li4zi3楼主2024/12/29 21:28

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;
}
2024/12/29 21:28
加载中...