DAG优化

骑猪看日落 2022-05-24 04:08 149阅读 0赞

>     DAG优化
> 
> Time Limit: 1000 ms Memory Limit: 65536 KiB
> 
> Problem Description 大家都学过了代码优化，其中有一个DAG优化，这次我们就练习这个操作。
> 
> Input 输入第一行为一个整数ｎ(n < 100)，表示该组输入的表达式的个数
> 
> 之后ｎ行为表达式，每个变量为一个字母，表达式仅包括二元运算 + - \* /
> 
> 例如：A=B+C
> 
> Output 通过构造DAG图，进行代码优化，只需要保留AB，删除无用变量，删除变量时，尽量保留最早出现的变量。
> 
> PS:保证AB的值不同
> 
> Sample Input  
> 3  
> B=B+B  
> A=C+C  
> B=B+B  
> A=C+C

#include <bits/stdc++.h>
    using namespace std;
    int n;
    int cnt;
    struct Node
    {
        char id;
        int left = -1, right = -1;
        vector<char> var;
    } node[110];
    
    bool find_var(int i,char c)
    {
        for(char j : node[i].var)if(j == c)return 1;
        return 0;
    }
    
    int add_node(char c)
    {
        for(int i = cnt-1; i >= 0; --i)
            if(node[i].id == c || find_var(i,c))return i;
        node[cnt].id = c;
        return cnt++;
    }
    
    void add_operator(char c,char op,int l,int r)
    {
        for(int i = cnt-1; i >= 0; --i)
            if(node[i].left == l && node[i].right == r && node[i].id == op)
            {
                node[i].var.push_back(c);
                return ;
            }
        node[cnt].id = op;
        node[cnt].var.push_back(c);
        node[cnt].left = l;
        node[cnt].right = r;
        cnt++;
    }
    char s[10];
    char ans[110][10];
    bool flag[110];
    void dfs(int x)
    {
        if(node[x].left != -1)
        {
            flag[x] = 1;
            dfs(node[x].left);
            dfs(node[x].right);
        }
    }
    
    int main()
    {
        cnt = 0;
        scanf("%d",&n);
        for(int i = 0; i < n; ++i)
        {
            scanf("%s",s);
            int l = add_node(s[2]);
            int r = add_node(s[4]);
            add_operator(s[0],s[3],l,r);
        }
        for(int i = 0; i < cnt; ++i)
        {
            if(node[i].left != -1)
            {
                ans[i][0] = node[i].var[0];
                ans[i][1] = '=';
                Node ll = node[node[i].left],rr = node[node[i].right];
                ans[i][2] = ll.var.size() > 0 ? ll.var[0] : ll.id;
                ans[i][3] = node[i].id;
                ans[i][4] = rr.var.size() > 0 ? rr.var[0] : rr.id;
                ans[i][5] = 0;
            }
        }
        for(int i = cnt-1; i >= 0; --i)
        {
            if(ans[i][0] == 'A')
            {
                dfs(i);
                break;
            }
        }
        for(int i = cnt-1; i >= 0; --i)
        {
            if(ans[i][0] == 'B')
            {
                dfs(i);
                break;
            }
        }
        for(int i = 0; i < cnt; ++i)if(flag[i])puts(ans[i]);
        return 0;
    }