3500N

Description

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

Input

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

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

例如：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

  1 #include <iostream>
  2 #include <string.h>
  3 #include <vector>
  4 
  5 using namespace std;
  6 
  7 struct Node
  8 {
  9     char id;
 10     int left=-1, right=-1;
 11     vector <char> ve;
 12 }node[105];
 13 int book[105], top;
 14 char re[105][15];
 15 
 16 int fin(int x, char c)
 17 {
 18     if(node[x].id==c) return 1;
 19     int i, len;
 20     len = node[x].ve.size();
 21     for(i=0;i<len;i++)
 22     {
 23         if(node[x].ve[i]==c) break;
 24     }
 25     if(i<len) return 1;
 26     else return 0;
 27 }
 28 
 29 int add_node(char x)
 30 {
 31     int i;
 32     for(i=0;i<top;i++)
 33     {
 34         if(fin(i, x)) break;
 35     }
 36     if(i<top) return i;
 37     else
 38     {
 39         Node nod;
 40         nod.id = x;
 41         node[top++] = nod;
 42         return top-1;
 43     }
 44 }
 45 
 46 void add_op(char re, char op, int left, int right)
 47 {
 48     int i;
 49     for(i=0;i<top;i++)
 50     {
 51         if(node[i].id==op&&node[i].left==left&&node[i].right==right) break;
 52     }
 53     if(i<top) node[i].ve.push_back(re);
 54     else
 55     {
 56         Node nod;
 57         nod.id = op;
 58         nod.left = left;
 59         nod.right = right;
 60         nod.ve.push_back(re);
 61         node[top++] = nod;
 62     }
 63 }
 64 
 65 char haha(int x)
 66 {
 67     char c = node[x].ve[0];
 68     int len = node[x].ve.size();
 69     for(int i=0; i<len; i++)
 70     {
 71         if(node[x].ve[i] == 'A' || node[x].ve[i] == 'B') c = node[x].ve[i];
 72     }
 73     return c;
 74 }
 75 
 76 void dfs(int x)
 77 {
 78     if(node[x].left!=-1)
 79     {
 80         book[x] = 1;
 81         dfs(node[x].left);
 82         dfs(node[x].right);
 83     }
 84 }
 85 
 86 int main()
 87 {
 88     int n, i, ll, rr;
 89     char s[15];
 90     cin >> n;
 91     top = 0;
 92     memset(book, 0, sizeof(book));
 93     for(i=0;i<n;i++)
 94     {
 95         cin >> s;
 96         ll = add_node(s[2]);
 97         rr = add_node(s[4]);
 98         add_op(s[0], s[3], ll, rr);
 99     }
100     for(i=0;i<top;i++)
101     {
102         if(node[i].left==-1) continue;
103         re[i][0] = haha(i);
104         re[i][1] = '=';
105         Node le, ri;
106         le = node[node[i].left];
107         ri = node[node[i].right];
108         re[i][2] = le.left==-1 ? le.id : haha(node[i].left);
109         re[i][3] = node[i].id;
110         re[i][4] = ri.right==-1 ? ri.id : haha(node[i].right);
111         re[i][5] = '';
112     }
113     for(i=top-1;i>=0;i--)
114     {
115         if(re[i][0]=='A')
116         {
117             dfs(i);
118             break;
119         }
120     }
121     for(i=top-1;i>=0;i--)
122     {
123         if(re[i][0]=='B')
124         {
125             dfs(i);
126             break;
127         }
128     }
129     for(i=0;i<top;i++)
130     {
131         if(book[i]) cout << re[i] << endl;
132     }
133     return 0;
134 }