DAG最適化-詳細

DAG最適化
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
コード最適化を学んだことがありますが、その中にDAG最適化があります.今回はこの操作を練習します.
Input
第1の動作の整数n(n<100)を入力し、そのグループが入力した式の個数を表す
その後n動作式、各変数は1文字で、式は2元演算+-*/のみを含む
例えば、A=B+C
Output
DAG図を構築することで,コード最適化を行い,ABを保持し,不要な変数を削除し,変数を削除する際には,最も早く出現した変数をできるだけ保持する.
PS:ABの値が異なることを保証する
Sample Input
3 A=B+C B=B+B A=C+C
Sample Output
B=B+B A=C+C私はネット上で多くのコードACという問題を見て、すべて90行近くで、しかも注釈がなくて、とても理解しにくいように見えて、長い間探してやっと1つの異なる他の書き方のブロガーのブログを発見して、しかも40行余りしかなくて、しかし注釈もなくて、私は1時間以上かけて理解して、それからみんなに注釈をつけました

#include 
//      ，          A,B   ，   A,B          ，
//  A=C+D, C=*** D=***        ，
using namespace std;
int print[100];//    ，     0  1, 1                
char formula[100][20];//             String formula[];
int revelant[300];//        A,B   A,B      ACCII    ，  1，  revelant['A']=1,   revelant[65]=1;
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
        scanf("%s",formula[i]);//              forMula 
    memset(revelant,0,sizeof(revelant));
    memset(print,0,sizeof(print));
    revelant['A']=revelant['B']=1;//  revelant[65]=1,revelant[66]=1,
    for(int i=n; i>=1; i--)//           A,B     ，          
    {//   A,B     ，  formula[i]      A,B  ， print[i]=1

        if(revelant[(int)formula[i][0]]==1)
        {
            print[i]=1;
            revelant[(int)formula[i][0]]=0;//           ,  A=B+C,A=D+F,            
            revelant[(int)formula[i][2]]=1;
            revelant[(int)formula[i][4]]=1;
        }
    }
    for(int i=1; i<=n; i++)
    {

        if(print[i]==1)
        {

            if(formula[i][0]=='A'||formula[i][0]=='B')//   A/B=D+C，     A,B,        ，  A=***,              
                continue;//
            for(int j=1; j<=i-1; j++)
            {

                if(formula[i][2]==formula[j][2]&&formula[i][3]==formula[j][3]&&formula[i][4]==formula[j][4])//  A=C+D,C=G+F    ,i  *=G+F     ，       ，        。  break
                {
                    print[j]=1;//       ，           ，   1，          
                    print[i]=0;
                    for(int k=i+1; k<=n; k++)//         i C=G+F, j  *=G+F
                    {//   i     ，       C     *，   i+3  D=C+B,     D=*+B
                        if(formula[k][0]==formula[i][0])break;
                        if(formula[k][2]==formula[i][0]) formula[k][2]=formula[j][0];
                        if(formula[k][4]==formula[i][0]) formula[k][4]=formula[j][0];

                    }
                    break;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {//     1   

        if(print[i]==1)
            printf("%s
",formula[i]);
    }

}