H wcy的表达式

H题 wcy的表达式

解题思路

• 利用链式前向星构造树形结构
• 深度优先遍历该树，每遍历到一个节点，计算根节点到当前节点路径上的公式值，并纳入res[i],i为当前节点编号。
  • 计算当前公式，可以始终维持一个数栈和操作栈，每次遇到栈顶操作符的优先级 >= 当前操作符优先级 时，将数栈和操作栈弹出计算公式，并将所得值放回数栈中。
  • 例如 当前操作是+ 栈顶操作符* 满足条件，弹出数栈中两个值，操作符栈一个值，并计算 ，15放回数栈中，并将+入操作符栈，6入数栈。 反之， 栈顶操作符+优先级 < 优先级，直接将压入操作栈，6压入数栈。
  • 计算到该节点，直接计算目前保存在数栈和操作栈中的公式即可。操作栈中的运算符的优先级一定是 升序排列的，因为一旦出现逆序在第2步中就已经消除了。
• 除法都转换成乘法，所得数对MOD=1e9+7取余，所以数x的逆元就是 , 式

利用链式前向星构造树结构

训练营一 C 红和蓝

int n,tot = 0;
int head[SIZE];
struct star{
    int to, next;
    char op;// 权值是 边操作
} edge[SIZE];
void addedge(int x, int y, char op) {
    edge[++tot].to = y;
    edge[tot].next = head[x];
    edge[tot].op = op;
    head[x] = tot;
}

实现代码

#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int SIZE=1e5+10;
long long  qsm(long long a, long long b) {
    long long sum = 1, t = a;
    while (b) {
        if (b&1) sum = sum * t % MOD;
        t = t * t % MOD;
        b >>= 1;
    }
    return sum;
}
int n,tot = 0;
int head[SIZE];
struct star{
    int to, next;
    char op;// 权值是 边操作
} edge[SIZE];
void addedge(int x, int y, char op) {
    edge[++tot].to = y;
    edge[tot].next = head[x];
    edge[tot].op = op;
    head[x] = tot;
}
int data[SIZE];
char op[SIZE];
int fa[SIZE];
int res[SIZE];
int cmp(char x, char y) {
    if  ((x == '+' || x == '-') && ( y=='*' || y=='/' )) {
        return -1; // 暂时不可以计算
    } else if ((y == '+' || y == '-') && ( x=='*' || x=='/' )) {
        return 1; // 可以计算 
    } else return 0; // 可以计算 
}
long long ni(int x, int p) {
    return qsm(x, p-2);
}
int doop(int x, int y, char op) {
    //printf("%d %c %d \t", x, op, y);
    if (op == '+') return ((long long)x+y)%MOD;
    else if (op == '-') return ((long long)x-y+MOD)%MOD;
    else if (op == '*') return ((long long)x*y)%MOD;
    else if (op == '/') return ((long long)x*ni(y,MOD))%MOD;

    return -1;
}
int compute(vector<char> opp, vector<int> number) {
    int cur = -1;
    while (!opp.empty()) {
        char c = opp.back(); opp.pop_back();
        int x = number.back(); number.pop_back();
        int y = number.back(); number.pop_back();
        cur = doop(y, x, c);
        number.push_back(cur);
    }
    //if (number.empty()) cur = data[1];
    if (opp.empty()) cur = number.back();
    return cur;
}
void dfs1(int x, int fat, vector<char> opp, vector<int> number) {


    while (!opp.empty() && cmp(op[ x ], opp.back() ) <= 0 ) {
            char c = opp.back(); opp.pop_back();
            int x = number.back(); number.pop_back();
            int y = number.back(); number.pop_back();
            int kl = doop(y, x, c);
            number.push_back(kl);
        }

    number.push_back(data[x]);

    if (x!=1) opp.push_back( op[x] );

    res[x] = compute(opp, number);

    // 深度优先遍历更新当前节点的值 
    for (int i=head[x]; i!=-1; i= edge[i].next) {
        if (edge[i].to == fat) continue;
        dfs1(edge[i].to, x, opp, number);
    }

}

int main() {
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i=1;i<=n;i++) scanf("%d", &data[i]);
    for (int i=2;i<=n;i++) scanf("%d", &fa[i]);
    scanf(" %s", op+2);
    for (int i=2; i<=n; i++) {
        addedge(fa[i], i, op[i]); // 添加父亲到当前节点的边
    }
    vector<char> op;
    vector<int> number;
    res[1] = data[1];
    dfs1(1, 0, op, number);
    for (int i=1;i<=n;i++) {
        if (i==1) printf("%d", res[i]);
        else printf(" %d", res[i]);
    }
    return 0;
}