Вычисление выражения после директивы EQU
Есть такая задача:
Для повышения читабельности программ на языке ассемблера программисты пользуются именами. Для задания имени можно воспользоваться директивой EQU: имя EQU выражение, где имя – это определяемое программистом символическое имя, а выражение позволяет вычислить значение имени. Пусть имя начинается с латинской буквы и содержит до 8 латинских букв или цифр. Выражение может быть целым числом, другим именем, суммой и/или разностью некоторого количества имен и/или целых положительных чисел. При этом к моменту обработки данной строки имена, входящие в выражение, могут еще не получить своих значений. Однако после обработки всех строк текста программы все имена получают свои значения. Гарантируется, что отсутствуют перекрестные ссылки среди выражений: если имя1 требует знания значения имя2, то имя2 не зависит от значения имя1. Требуется обработать последовательность директив EQU.
Пример входных данных:
Alpha EQU 5
Beta EQU Gamma–Delta+3
Gamma EQU Alpha+5
Delta EQU 17-Gamma+9
Пример выходных данных:
Alpha 5
Beta -3
Gamma 10
Delta 16
Я решил данную задачу, что мое решение проходит не все тесты. На одном из них выдает не правильный ответ, а на остальных превышение лимита по памяти. Так вот, я не знаю, в чем проблема. Предположу, что превышение лимита по памяти происходит в связи с чрезмерным стеком вызовов рекурсивной функций.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct var_name
{
string name = "";
int value = 0;
bool full = false;
};
struct reference
{
string var = "";
vector<string> ref;
};
int findVar(const string& name, const vector<var_name>& names) {
int res = -1;
for (int i = 0; i < names.size(); i++) {
if (names[i].name == name)
return i;
}
return res;
}
int findRef(const string& name, const vector<reference>& references) {
for (int i = 0; i < references.size(); i++) {
if (references[i].var == name)
return i;
}
}
void calculateExpression(const vector<string>& operations, vector<reference>& references, vector<var_name>& names, const string& name) {
var_name new_var;
reference new_ref;
new_var.full = true;
new_ref.var = name;
for (int i = 0; i < operations.size(); i++) {
if (isdigit(operations[i][0])) { // число
new_var.name = name;
new_var.value += stoi(operations[i]);
}
else { // переменная
int mult = 1;
string oper = operations[i];
if (operations[i][0] == '-') {
mult = -1;
oper = operations[i].substr(1, operations[i].size());
}
int indexVar = findVar(oper, names);
if (indexVar == -1) {
new_ref.ref.push_back(operations[i]);
new_var.full = false;
new_var.name = name;
}
else {
new_var.name = name;
new_var.value += mult * names[indexVar].value;
}
}
}
names.push_back(new_var);
if (!new_ref.ref.empty())
references.push_back(new_ref);
}
int calculateOther(const string& name, const vector<reference>& references, vector<var_name>& names) {
int indexRef = findRef(name, references), indexCurVar = findVar(name, names);
for (int i = 0; i < references[indexRef].ref.size(); i++) {
int mult = 1;
string oper = references[indexRef].ref[i];
if (references[indexRef].ref[i][0] == '-') {
mult = -1;
oper = references[indexRef].ref[i].substr(1, references[indexRef].ref[i].size());
}
int indexVar = findVar(oper, names);
if (names[indexVar].full) {
names[indexCurVar].value += mult * names[indexVar].value;
}
else {
int indexNewRef = findRef(references[indexRef].ref[i], references);
names[indexCurVar].value += mult * calculateOther(references[indexNewRef].var, references, names);
}
}
names[indexCurVar].full = true;
return names[indexCurVar].value;
}
int main()
{
string current = "", c_name = "";
vector<string> cur_operations;
vector<var_name> names;
vector<reference> references;
var_name c_var;
int i = 0;
while (getline(cin, current) && !current.empty()) {
/* Обработка строки. Выделение названия переменной и операции */
while (current[i] != ' ' && current[i] != '\t') // выделяем имя переменной
c_name += current[i++];
i = current.find("EQU") + 3;
while (current[i] == ' ' || current[i] == '\t') i++;
while (i < current.size()) {
string tmp_operation = "";
if (current[i] == '-' || current[i] == '+') {
if (current[i] != '+')
tmp_operation += current[i];
i++;
}
while (current[i] != '-' && current[i] != '+' && i < current.size()) tmp_operation += current[i++];
cur_operations.push_back(tmp_operation);
}
calculateExpression(cur_operations, references, names, c_name); // генерируем значения и зависимости на первом проходе
cur_operations.clear();
c_name = "";
i = 0;
}
// просчет переменных, зависимых от других
bool f = true;
for (int i = 0; i < references.size(); i++) {
if (!names[findVar(references[i].var, names)].full)
calculateOther(references[i].var, references, names);
}
for (int i = 0; i < names.size(); i++)
cout << names[i].name << ' ' << names[i].value << '\n';
return 0;
}