N - DAG优化【编译原理】

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

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