大家都学过了代码优化,其中有一个DAG优化,这次我们就练习这个操作。
输入第一行为一个整数n(n < 100),表示该组输入的表达式的个数
之后n行为表达式,每个变量为一个字母,表达式仅包括二元运算 + - * /
例如:A=B+C
通过构造DAG图,进行代码优化,只需要保留AB,删除无用变量,删除变量时,尽量保留最早出现的变量。
PS:保证AB的值不同
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;
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] = '\0';
}
}
// 保留所需要变量
// 题目中要求保留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;
}