N - DAG优化

Description
大家都学过了代码优化,其中有一个DAG优化,这次我们就练习这个操作。

Input
输入第一行为一个整数n(n < 100),表示该组输入的表达式的个数

之后n行为表达式,每个变量为一个字母,表达式仅包括二元运算 + - * /

例如:A=B+C

Output
通过构造DAG图,进行代码优化,只需要保留AB,删除无用变量,删除变量时,尽量保留最早出现的变量。

PS:保证AB的值不同

Sample
Input

3
A=B+C
B=B+B
A=C+C

Output

B=B+B
A=C+C
#include <bits/stdc++.h>
using namespace std;

string s;
int flag[110];
char ans[110][110];
int n,top=0;

struct node
{
    int l=-1,r=-1;
    char id;
    vector<char>val;

} t[110];

int add(char ch)
{
    for(int i=0; i<top; i++)
    {
        if(ch==t[i].id)return i;
        for(char c:t[i].val)if(ch==c)return i;
    }
    t[top].id=ch;
    return top;
}


void addop(char op,char ch,int l,int r)
{
    for(int i=0; i<top; i++)
    {
        if(t[i].id==op&&t[i].l==l&&t[i].r==r)
        {
            t[i].val.push_back(ch);
            return;
        }

    }
    t[top].id=op;
    t[top].l=l;
    t[top].r=r;
    t[top].val.push_back(ch);
    top++;
}

void dfs(int x)
{
    if(t[x].l!=-1)
    {
        flag[x]=1;
        dfs(t[x].l);
        dfs(t[x].r);
    }
}

char exist(int x)
{
   for(char c:t[x].val)if(c=='A'||c=='B')return c;
    return t[x].val[0];
}

int main()
{
    int i;
    cin>>n;
    for(i=0; i<n; i++)
    {
        cin>>s;
        int l=add(s[2]);top++;
        int r=add(s[4]);top++;
        addop(s[3],s[0],l,r);
    }
    for(i=0; i<top; i++)
    {
        if(t[i].l!=-1)
        {
            ans[i][0]=exist(i);
            ans[i][1]='=';
            ans[i][2]=t[t[i].l].val.size()>0?exist(t[i].l):t[t[i].l].id;
            ans[i][3]=t[i].id;
            ans[i][4]=t[t[i].r].val.size()>0?exist(t[i].r):t[t[i].r].id;
            ans[i][5]='\0';
        }
    }
    for(i=top-1; i>=0; i--)
    {
        if(ans[i][0]=='A')
        {
            dfs(i);
            break;
        }
    }
    for(i=top-1; i>=0; i--)
    {
        if(ans[i][0]=='B')
        {
            dfs(i);
            break;
        }
    }
    for(i=0; i<top; i++)
    {
        if(flag[i]) cout<<ans[i]<<endl;
    }

}
上一篇:7.5 有向无环图


下一篇:前沿: nature刊掀起DAG热, 不掌握就遭淘汰无疑!因果关系研究的图形工具!