3500P

Description

通过三地址代码序列生成计算机的目标代码,在生成算法中,对寄存器的使用顺序为:寄存器中存有 > 空寄存器 > 内存中存有 > 以后不再使用 > 最远距离使用

Input

单组输入,给定输出的三地址代码的个数和寄存器的个数.所有的变量为大写字母,寄存器的数量不超过9

Output

参照示例格式输出,不需要将最后的寄存器中的值写回内存

不再使用变量不用写回内存

Sample

Input

4 2
T:=A-B
U:=A-C
V:=T+U
W:=V+U

Output

LD R0, A
SUB R0, B
LD R1, A
SUB R1, C
ADD R0, R1
ADD R0, R1

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int n, m, top;
 6 char s[105][15], a[105]={''};
 7 
 8 int find1(char c)
 9 {
10     int i;
11     for(i=0;i<top;i++)
12     {
13         if(a[i]==c) return i;
14     }
15     return -1;
16 }
17 
18 int show(int st, char c)
19 {
20     int i;
21     for(i=st;i<n;i++)
22     {
23         if(s[i][3]==c||s[i][5]==c) return i;
24     }
25     return n;
26 }
27 
28 int find2(char c, int st)
29 {
30     if(top<m) return top++;
31     int i, maxx=-1, maxi, k;
32     for(i=0;i<m;i++)
33     {
34         k = show(st, a[i]);
35         if(k>maxx)
36         {
37             maxx = k;
38             maxi = i;
39         }
40     }
41     return maxi;
42 }
43 
44 int main()
45 {
46     int i, x, y;
47     top = 0;
48     cin >> n >> m;
49     for(i=0;i<n;i++)
50     {
51         cin >> s[i];
52     }
53     for(i=0;i<n;i++)
54     {
55         x = find1(s[i][3]);
56         if(x==-1)
57         {
58             x= find2(s[i][3], i);
59             if(a[x]!=''&&show(i, a[x])!=n) 
60             {
61                 printf("ST R%d, %c
", x, a[x]);
62                 a[x] = '';
63             }
64             printf("LD R%d, %c
", x, s[i][3]);
65         }
66         char op;
67         op = s[i][4];
68         if(op=='+') printf("ADD");
69         else if(op=='-') printf("SUB");
70         else if(op=='*') printf("MUL");
71         else printf("DIV");
72         y = find1(s[i][5]);
73         if(y==-1) printf(" R%d, %c
", x, s[i][5]);
74         else printf(" R%d, R%d
", x, y);
75         a[x] = s[i][0];
76     }
77     return 0;
78 }