N - DAG优化
Description
大家都学过了代码优化，其中有一个DAG优化，这次我们就练习这个操作。
Input
输入第一行为一个整数ｎ(n < 100)，表示该组输入的表达式的个数
之后ｎ行为表达式，每个变量为一个字母，表达式仅包括二元运算 - * /
例如：A=B C
Output
通过构造DAG图，进行代码优化，只需要保留AB，删除无用变量，删除变量时，尽量保留最早出现的变量。
PS:保证AB的值不同
Sample
Input
代码语言：javascript复制3
A=B C
B=B B
A=C COutput
代码语言：javascript复制B=B B
A=C C#include <bits/stdc .h>
using namespace std;
int cnt,n; // cnt 为当前结点的个数，n为输入的表达式个数
char s[10]; //临时输入
char ans[101][101]; // 最后输出的优化后的表达式
bool flas[101]; //用于记录那些表达式最后可以输出
struct st{
char id; // 结点的值
int left = -1; // left 和 right 都是存放的标号，即左/右子树所在的标号
int right = -1;
vector<char>var;
}node[101];
// i 是第i个结点，c是当前查找的符号
bool find_var(int i, char c)
{
// 一个结点可能有多个标记
int len = node[i].var.size();
for(int k = 0; k < len; k )
{
if(node[i].var[k] == c)
{
// 找到
return true;
}
}
return false;
}
// 建立结点
// add_node 返回的值时该结点的标号，也就是位置
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 --)
{
//如果该表达式已经存在，将该表达式左边的值放到结点的var中即可。
if(op == node[i].id && node[i].left == l && node[i].right == r)
{
node[i].var.push_back(c);
return ;
}
}
// 如果没有，则需要把整个表达式都加进去
// 形状是结点为操作符，左右结点为操作数，结果存到父节点的var中
node[cnt].id = op;
node[cnt].left = l;
node[cnt].right = r;
node[cnt].var.push_back(c);
cnt ;
}
// 保留变量标记
void dfs(int i){
// 如果保留的变量需要使用该表达式，则标记为1，保留下来
if(node[i].left != -1)
{
flas[i] = 1;
dfs(node[i].left);
dfs(node[i].right);
}
}
// ok函数
char ok(int i)
{
int len = node[i].var.size();
for(int k = 0; k < len; k )
{
// 遍历i结点这个地方是不是有A||B，如果有的话，就说明这个值就没用了，用A||B就行
if(node[i].var[k] == 'A' || node[i].var[k] == 'B')
{
return node[i].var[k];
}
}
// 如果没有那就暂时保存这个值
return node[i].var[0];
}
int main()
{
cnt = 0;
cin >> n;
for(int i = 0; i < n; i )
{
cin >> s;
// 使用add_node建立结点
int l = add_node(s[2]);
int r = add_node(s[4]);
// 将表达式构成树
// 左右的l、r 使用的就是两个变量存在的标号
add_operator(s[0],s[3],l,r);
}
for(int i = 0; i < cnt; i )
{
// 保留有左子树的,有左子树情况就是一个表达式的表示
if(node[i].left != -1){
// 搞定复写的另一种，比如c = d d,a = d d,b = e c
// 这时候确定存在ans[i][0]的是a，而不是c
ans[i][0] = ok(i);
ans[i][1] = '=';
// node[i] 是由其左右结点运算得来的
st ll = node[node[i].left];
st rr = node[node[i].right];
// 如果这个结点的左子树不是空的，那操作数就是ok(node[i].left)
//就是判断c = d d,a = d d,b = e c是否将c换成a
// 如果是空的，那就是左子树本身的值，即ll.id
ans[i][2] = ll.left != -1 ? ok(node[i].left) : ll.id;
ans[i][3] = node[i].id;
ans[i][4] = rr.left != -1 ? ok(node[i].right) : rr.id;
ans[i][5] = ' ';
}
}
// 保留所需要变量
// 题目中要求保留A、B
for(int i = cnt - 1; i >= 0; i --)
{
// 把A能用的表达式或者值进行标记
if(ans[i][0] == 'A')
{
dfs(i);
break;
}
}
for(int i = cnt - 1; i >= 0; i --)
{
// 把B能用的表达式或者值进行标记
if(ans[i][0] == 'B')
{
dfs(i);
break;
}
}
for(int i = 0; i < cnt; i )
{
if(flas[i])
{
puts(ans[i]);
}
}
return 0;
}
