PTA L3-023计算图

题意

给一个表达式的计算图，和输入变量的值。求解表达式的值和对每个输入变量的偏导。
题目链接

如何计算值

从输入变量正向拓扑排序，就可以保证在计算某个节点的值前，它的父节点计算过。于是就可以通过运算符计算当前节点的值。

第一个优化

运算符有６种，用if-else 不美观，可写６个函数，然后存在函数指针数组里。
运算符有单目和双目，参数不一致，可用数组来存放参数

如何计算梯度

假设终点为f
偏导法则 f_x = f_u*u_x+f_v*v_x+...
所以对于节点ｕ，已知f_u，可以更新它的父节点v的fv,fv+=f_u*u_v，当ｖ的儿子都遍历过后。f_v得到最终答案
所以可以使用从f逆向拓扑排序遍历。

第二个优化

更新父节点的偏导值时也可以使用函数指针数组
关键代码

struct Node{
    int cmd;
    double v, fv;
    Node* pa[2];
};
double (*f[10])(Node** pa)={NULL,add,minus, mut,exp_, ln_, sin_};
void (*Df[10])(Node** pa, double fv)={NULL, Dadd, Dminus, Dmut, Dexp_, Dln_, Dsin_};
int q[MAXN];
int topo() {
    int l=0, r=0;
    for(int i=0; i<n; i++) {
        if(!in[i]) q[r++]=i;
    }
    while(l<r) {
        int u=q[l++];
        if(nodes[u].cmd) {
            nodes[u].v = f[nodes[u].cmd](nodes[u].pa);
        }
        for(int i=0; i<G[u].size(); i++) {
            int v=G[u][i];
            --in[v];
            if(in[v]==0) q[r++]=v;
        }
    }
    return q[r-1];
}
void Dtopo(int s) {
    int l=0, r=0;
    q[r++]=s;
    while(l<r) {
        int u=q[l++];
        if(nodes[u].cmd) {
            Df[nodes[u].cmd](nodes[u].pa, nodes[u].fv);
        }
        for(int i=0; i<IG[u].size(); i++) {
            int v=IG[u][i];
            --out[v];
            if(!out[v]) q[r++] = v;
        }
    }
}