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;
}
}