1#include <bits/stdc++.h>
2using namespace std;
3vector<string> cg;
4stack<int> freereg;
5map<int, char> varreg;
6int Prec(char ch)
7{
8 switch (ch)
9 {
10 case '+':
11 case '-':
12 return 1;
13 case '*':
14 case '/':
15 return 2;
16 }
17 return -1;
18}
19string to_string1(int v)
20{
21 ostringstream oss;
22 oss << v;
23 return oss.str();
24}
25string convertsymbol(char ch)
26{
27 switch (ch)
28 {
29 case '+':
30 return "ADD";
31 case '-':
32 return "SUB";
33 case '*':
34 return "MUL";
35 case '/':
36 return "DIV";
37 }
38 return "";
39}
40string infixToPostfix(string exp)
41{
42 string result = "";
43 stack<char> stack;
44 for (int i = 0; i < exp.length(); i++)
45 {
46 char c = exp[i];
47 if (isalnum(c))
48 result += c;
49 else if (c == '(')
50 stack.push(c);
51 else if (c == ')')
52 {
53 while (!stack.empty() && stack.top() != '(')
54 {
55 result += stack.top();
56 stack.pop();
57 }
58 if (!stack.empty() && stack.top() != '(')
59 return "Invalid expression";
60 else
61 stack.pop();
62 }
63 else
64 {
65 while (!stack.empty() && Prec(c) <= Prec(stack.top()))
66 {
67 result += stack.top();
68 stack.pop();
69 }
70 stack.push(c);
71 }
72 }
73 while (!stack.empty())
74 {
75 result += stack.top();
76 stack.pop();
77 }
78 return result;
79}
80
81
82int load(char operand)
83{
84 string instr = "";
85 map<int, char>::iterator it = varreg.begin();
86 while (it != varreg.end())
87 {
88 if (it->second == operand) // use the same reg
89 return it->first;
90 it++;
91 }
92 int reg = freereg.top();
93 instr += "LD R" + to_string1(reg) + ", " + operand;
94 varreg[reg] = operand;
95 freereg.pop();
96 cg.push_back(instr);
97 return reg;
98}
99bool found(vector<pair<char, string>> icg, int i, char var)
100{
101 for (int j = i + 1; j < icg.size(); j++)
102 {
103 string expr = icg.at(j).second;
104 for (int k = 0; k < expr.length(); k++)
105 if (expr[k] == var)
106 return true;
107 }
108 return false;
109}
110int main()
111{
112 vector<pair<char, string>> icg;
113 string start;
114 string eq;
115 string input;
116 cin >> start;
117 cin >> eq;
118 cin >> input;
119 string temp = "";
120 char t = 'p';
121 int k = 1;
122 string postfix = infixToPostfix(input);
123 for (int i = 0; i < postfix.length(); i++)
124 {
125 string expr = "";
126 if (!isalpha(postfix[i]))
127 {
128 expr += temp[temp.length() - 2];
129 expr += postfix[i];
130 expr += temp[temp.length() - 1];
131 temp = temp.substr(0, temp.length() - 2);
132 int flag = 0;
133 for (int j = 0; j < icg.size(); j++)
134 {
135 if (icg.at(j).second == expr)
136 {
137 temp += icg.at(j).first;
138 flag = 1;
139 break;
140 }
141 }
142 if (flag == 0)
143 {
144 icg.push_back(make_pair(t, expr));
145 temp += t++;
146 }
147 }
148 else
149 temp += postfix[i];
150 }
151
152
153 icg.back().first = start[0];
154 for (int i = 10; i >= 1; i--)
155 freereg.push(i);
156 for (int i = 0; i < icg.size(); i++)
157 {
158 string expr = icg.at(i).second;
159 int reg1 = load(expr[0]);
160 int reg2 = load(expr[2]);
161 string instr = "";
162 bool r1f = found(icg, i, expr[0]);
163 bool r2f = found(icg, i, expr[2]);
164
165
166 if (!r1f)
167 {
168 instr += convertsymbol(expr[1]) + " R" + to_string1(reg1) + ", R" + to_string1(reg1) + ", R" + to_string1(reg2);
169 varreg[reg1] = icg.at(i).first;
170 if (!r2f)
171 {
172 if (reg1 != reg2)
173 {
174 freereg.push(reg2);
175 varreg.erase(reg2);
176 }
177 }
178 }
179 else if (!r2f)
180 {
181 instr += convertsymbol(expr[1]) + " R" + to_string1(reg2) + ", R" + to_string1(reg1) + ", R" + to_string1(reg2);
182 varreg[reg2] = icg.at(i).first;
183 }
184 else
185 {
186 int newreg = freereg.top();
187 instr += convertsymbol(expr[1]) + " R" + to_string1(newreg) + ", R" + to_string1(reg1) + ", R" + to_string1(reg2);
188 varreg[newreg] = icg.at(i).first;
189 freereg.pop();
190 }
191 cg.push_back(instr);
192 }
193 char result = icg.back().first;
194 string instr = "ST ";
195 instr += result;
196 instr += ", R" + to_string1(varreg.rbegin()->first);
197 cg.push_back(instr);
198 cout << endl;
199 for (int i = 0; i < cg.size(); i++)
200 cout << cg.at(i) << endl;
201 return 0;
202}
203