e-olymp 1072. Химические реакции

Условие

Задача взята с сайта e-olymp, полное условие можно прочитать здесь.

Входные данные

В первой строке находится формула — левая часть уравнения, во второй- одно число [latex]N (1 \leq N \leq 10)[/latex] — количество рассматриваемых правых частей, в каждой из последующих [latex]N[/latex] строк — одна формула — предполагаемая правая часть уравнения.

Длина формулы не превосходит [latex]100[/latex] символов, каждый отдельный химический элемент встречается всего не более [latex]10000[/latex] раз в каждой формуле.

(Примечание: понятие формулы в данном алфавите можно прочитать по ссылке выше.)

Выходные данные

Для каждой из [latex]N[/latex] заданных строк вывести одну строку вида

формула левой части==формула правой части

если общее количество вхождений каждого отдельного химического элемента в левую часть равно общему числу вхождений этого химического элемента в правую часть. В противном случае выведите:

формула левой части!=формула правой части

Здесь формула левой части должна быть заменена посимвольной копией формулы левой части, как она дана в первой строке входного файла, а формула правой части — замещена точной копией формулы правой части, как она дана во входном файле. В строках не должно быть пробелов.

Решение (вспомогательные функции)

Так как задача достаточно объемная, напишем ряд вспомогательных функций:

Определяет, является ли символ цифрой.

bool isDigit(char c);

1

bool isDigit(char c);
Определяет, является ли символ буквой в верхнем регистре.

bool isUpperCaseLetter(char c);

1

bool isUpperCaseLetter(char c);
Определяет, является ли символ буквой в нижнем регистре.

bool isLowerCaseLetter(char c);

1

bool isLowerCaseLetter(char c);
Будем хранить содержимое формулы используя структуру map (карта), ключами будут выступать названия элементов (строки), значениями — количества их вхождений. Если элемента в карте нет, добавляем пару <элемент, кол-во>, иначе — прибавляем к старом числу вхождений новое. За это отвечает следующая функция.

void update(map<string, int> &map, string key, int value);

1

void update(map<string, int> &map, string key, int value);
Для простоты разобьем формулу на подформулы (по знаку [latex]+[/latex], если он встречается), и будем работать с каждой формулой по отдельности. Функция разбивает строку на подстроки по знаку [latex]+[/latex] и заполняет ими вектор [latex]storage[/latex] (так как мы не знаем кол-во подформул заранее, вектор предпочтительнее массива).

void split(string formula, vector<string> &storage);

1

void split(string formula, vector<string> &storage);
По условию, перед каждой подформулой может идти множитель, относящейся ко всей подформуле. Функция возвращает множитель ( [latex]1[/latex], если множитель не записан явно).

int getMultiplier(string formula);

1

int getMultiplier(string formula);
Основная функция. Добавляет в карту [latex]content[/latex] содержимое подформулы.

void getContent(string formula, int multiplier, map<string, int> &content);

1

void getContent(string formula, int multiplier, map<string, int> &content);
Обрабатывает формулу. Просто вызывает функции №[latex]6[/latex] и №[latex]7[/latex] по очереди для каждой из подформул (элементов из [latex]subformulas[/latex]).

void process(vector<string> subformulas, map<string, int> &content);

1

void process(vector<string> subformulas, map<string, int> &content);

Решение (основной алгоритм)

Все вспомогательные функции реализованы достаточно просто (см. код и комментарии). Рассмотрим основную функцию, алгоритм работы которой, по сути, почти является алгоритмом решения задачи.

void getContent(string formula, int multiplier, map<string, int> &content);

1	void getContent(string formula, int multiplier, map<string, int> &content);

Тут:

[latex]formula[/latex] — подформула обрабатываемой формулы (без общего множителя);
[latex]multiplier[/latex] — множитель, определяется предыдущей функцией, перед вызовом данной;
[latex]content[/latex] — карта, куда записываются элементы всех подформул текущей формулы (доступ осуществляется по адресу).

Алгоритм разделяется на 2 случая, в зависимости от наличия скобок. Предположим, скобок в подформуле (далее — просто формуле) нет. Заведем переменные [latex]name[/latex] (название элемента. тип string) и [latex]coefficient[/latex] (задний коэффициент, тип string). Тогда, проходя по порядку по символам формулы, будем выполнять следующие действия в зависимости от текущего символа([latex]c[/latex]):

[latex]c[/latex] — цифра: добавляем его в конец строки [latex]coefficient[/latex];
[latex]c[/latex] — буква в нижнем регистре: добавляем его в конец строки [latex]name[/latex];
[latex]c[/latex] — буква в верхнем регистре: если строка [latex]name[/latex] — пустая (первый элемент в формуле), то добавляем его в конец строки [latex]name[/latex]. Иначе, сперва обнуляем [latex]name[/latex], потом добавляем. Тогда, если строка [latex]coefficient[/latex] — пустая, присваиваем [latex]coefficient=[/latex]»[latex]1[/latex]». Получаем количество вхождений элемента как [latex]multiplier*stoi(coefficient)[/latex], где stoi() — стандартная функция, преобразующая число к строке. Затем добавляем в карту элемент и полученное кол-во вхождений.

update(content, name, multiplier * stoi(coefficient));

140

update(content, name, multiplier * stoi(coefficient));

(Примечание: пункт [latex]3[/latex] для последнего элемента (кроме обновления значения [latex]name[/latex]) придется повторить отдельно.)

update(content, name, multiplier * stoi(coefficient));

153	update(content, name, multiplier * stoi(coefficient));

Если же в формуле имеются скобки, то:

Находим первую открывающую скобку.
Находим соответствующую ей закрывающую скобку.
Для выражения в скобках вычисляем задний коэффициент (см. код), заносим в переменную [latex]newMultiplier[/latex] значение множителя для выражения внутри скобок.
Рекурсивно вызываем функцию getContent() для:
1. Выражения перед открывающей скобкой, если формула не начинается с нее.
  
  getContent(formula.substr(0, begin - 1), multiplier, content);
  
  106
  
  getContent(formula.substr(0, begin - 1), multiplier, content);
  
  ([latex]begin[/latex] — номер первого символа внутри скобок.)
2. Выражения внутри скобок.
  
  getContent(formula.substr(begin, end - begin), newMultiplier, content);
  
  108
  
  getContent(formula.substr(begin, end - begin), newMultiplier, content);
  
  ([latex]end[/latex] — номер закрывающей скобки.)
3. Выражения после закрывающей скобки или заднего коэффициента, если присутствует (если только скобка/коэффициент не является концом формулы).
  
  getContent(formula.substr(afterEnd), multiplier, content);
  
  111
  
  getContent(formula.substr(afterEnd), multiplier, content);
  
  ([latex]afterEnd[/latex] — следующий после скобки/коэффициента символ.)

Этот алгоритм фактически является решением задачи. Теперь в методе [latex]main[/latex] надо всего лишь обработать главную формулу, а затем для каждого случая в цикле — сравниваемую с ней формулу, сравнив после содержимое их карт (сравнение осуществляется просто используя оператор сравнения ==). Обработка подразумевает последовательный вызов функций split() и process().

Тесты

№	Ввод	Вывод
1	C2H5OH+3O2+3(SiO2) 6 2CO2+3H2O+3SiO2 2C+6H+13O+3Si 99C2H5OH+3SiO2 3SiO4+C2H5OH C2H5OH+3O2+3(SiO2)+Ge 3(Si(O)2)+2CO+3H2O+O2	C2H5OH+3O2+3(SiO2)==2CO2+3H2O+3SiO2 C2H5OH+3O2+3(SiO2)==2C+6H+13O+3Si C2H5OH+3O2+3(SiO2)!=99C2H5OH+3SiO2 C2H5OH+3O2+3(SiO2)==3SiO4+C2H5OH C2H5OH+3O2+3(SiO2)!=C2H5OH+3O2+3(SiO2)+Ge C2H5OH+3O2+3(SiO2)==3(Si(O)2)+2CO+3H2O+O2
2	2H2O 5 HHOHHO 2H+H2+(O(O)) 2((H2)O) HOHHOHe H4O	2H2O==HHOHHO 2H2O==2H+H2+(O(O)) 2H2O==2((H2)O) 2H2O!=HOHHOHe 2H2O!=H4O
3	8Zn+Ar4+Ne 3 Ne(Ar2(Zn)4)2 2Ne(Ar2(Zn)4) Ne+2Zn2(((((Ar)))))2Zn2	8Zn+Ar4+Ne==Ne(Ar2(Zn)4)2 8Zn+Ar4+Ne!=2Ne(Ar2(Zn)4) 8Zn+Ar4+Ne==Ne+2Zn2(((((Ar)))))2Zn2

Код

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
using namespace std;

bool isDigit(char c) { return  c >= '0' && c <= '9'; }

bool isUpperCaseLetter(char c) { return  c >= 'A' && c <= 'Z'; }

bool isLowerCaseLetter(char c) { return  c >= 'a' && c <= 'z'; }

void update(map<string, int> &map, string key, int value)
{
    if (map.count(key)) //вернет 0 (false) если элемент не найден, иначе - 1 (true)
    {
        map.at(key) = map.at(key) + value; //обновляем значение элемента в карте
    }
    else
    {
        map.insert(make_pair(key, value)); //добавляем элемент в карту
    }
}

void split(string formula, vector<string> &storage)
{
    int begin = 0, length = 0;
    for (int i = 0; i < formula.length(); i++)
    {
        if (formula.at(i) == '+')
        {
            storage.push_back(formula.substr(begin, length));
            length = 1;
            begin = ++i;
        }
        else
        {
            length++;
        }
    }
    storage.push_back(formula.substr(begin, length));
}

int getMultiplier(string formula)
{
    int res = 0;
    for (int i = 0; i < formula.length(); i++)
    {
        if (isDigit(formula.at(i))) 
        {
            res *= 10;
            res += (formula.at(i) - '0'); //получаем из символа соответствующую цифру
        }
        else break;
    }
    return res == 0 ? 1 : res; //0 - если перед формулой нет множителя, тогда он должен быть 1
}

void getContent(string formula, int multiplier, map<string, int> &content)
{ 
    if (formula.find('(') != string::npos) //если есть скобки
    {
        int begin = formula.find('(') + 1; //первый символ внутри скобок
        int end;
        int bracketCounter = 1;
        for (int i = begin; true; i++)
        {
            if (formula.at(i) == '(')
            {
                bracketCounter ++;
            }
            else if (formula.at(i) == ')')
            {
                bracketCounter--;
                if (bracketCounter == 0)
                {
                    end = i; //находим соответствующую закрывающую скобку
                    break;
                }
            }
        }
        int newMultiplier = multiplier;
        int afterEnd = end + 1;
        int backCoefficient = 0; //вычисляем коэффициент за скобочным выражением
        for (int i = 1; true; i++)
        {
            if (end + i != formula.length() && isDigit(formula.at(end + i))) //пока есть числа за закрывающей скобкой, обновляем значение заднего коэффициента
            {
                backCoefficient *= 10;
                backCoefficient += (formula.at(end + i) - '0');
                afterEnd++;
            }
            else
            {
                if (backCoefficient == 0) //если чисел после закрывающей скобки нет, коэффициент равен 1
                {
                    backCoefficient++;
                }
                newMultiplier *= backCoefficient; //вычисляем новое значение множителя для выражения внутри скобок
                break;
            }
        }
        if (begin != 1)
        {
            getContent(formula.substr(0, begin - 1), multiplier, content); 
        }
        getContent(formula.substr(begin, end - begin), newMultiplier, content); 
        if (afterEnd < formula.length())
        {
            getContent(formula.substr(afterEnd), multiplier, content);
        }
    }
    else //если скобок нет
    {
        string name = "";
        string coefficient = "";
        for (char c : formula)
        {
            if (isDigit(c)) 
            {
                coefficient += c;
            }
            else if (isLowerCaseLetter(c)) 
            {
                name += c;
            }
            else if (isUpperCaseLetter(c))
            {
                if (name.empty()) 
                {
                    name += c;
                }
                else
                {
                    if (coefficient.empty()) 
                    {
                        coefficient = "1";
                    }
                    update(content, name, multiplier * stoi(coefficient));
                    name.clear();
                    name += c;
                    coefficient = "";
                }
            }
        }
        if (!name.empty())
        {
            if (coefficient.empty()) 
            {
                coefficient = "1";
            }
            update(content, name, multiplier * stoi(coefficient));
        }
    }
}

void process(vector<string> subformulas, map<string, int> &content)
{
    for (string subformula : subformulas) //для каждой подформулы:
    {
        int multiplier = getMultiplier(subformula); //вычисляем множитель перед ней
        if (multiplier != 1) //если множитель записан явно
        {
            getContent(subformula.substr(floor(log10(multiplier)+1)), multiplier, content); //передаем в функцию подформулу, начиная с первого символа, не относящегося к переднему множителю
        }
        else
        {
            getContent(subformula, multiplier, content); //иначе передаем подформулу целиком
        }
    }
}

int main() 
{
    string mainFormula;
    vector<string> mainSubformulas;
    map<string, int> mainContent;
    cin >> mainFormula;
    split(mainFormula, mainSubformulas);
    process(mainSubformulas, mainContent);
    int n;
    cin >> n;
    string formulaToCompare;
    vector<string> subformulasToCompare;
    map<string, int> contentToCompare;
    for (int i = 0; i < n; i++)
    {
        subformulasToCompare.clear(); //
        contentToCompare.clear();
        cin >> formulaToCompare;
        split(formulaToCompare, subformulasToCompare);
        process(subformulasToCompare, contentToCompare);
        cout << mainFormula << (mainContent == contentToCompare ? "==" : "!=") << formulaToCompare << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

#include <iostream>

#include <cmath>

#include <string>

#include <vector>

#include <map>

using namespace std;

bool isDigit(char c) { return c >= '0' && c <= '9'; }

bool isUpperCaseLetter(char c) { return c >= 'A' && c <= 'Z'; }

bool isLowerCaseLetter(char c) { return c >= 'a' && c <= 'z'; }

void update(map<string, int> &map, string key, int value)

{

if (map.count(key)) //вернет 0 (false) если элемент не найден, иначе - 1 (true)

{

map.at(key) = map.at(key) + value; //обновляем значение элемента в карте

}

else

{

map.insert(make_pair(key, value)); //добавляем элемент в карту

}

void split(string formula, vector<string> &storage)

{

int begin = 0, length = 0;

for (int i = 0; i < formula.length(); i++)

{

if (formula.at(i) == '+')

{

storage.push_back(formula.substr(begin, length));

length = 1;

begin = ++i;

}

else

{

length++;

}

storage.push_back(formula.substr(begin, length));

}

int getMultiplier(string formula)

{

int res = 0;

for (int i = 0; i < formula.length(); i++)

{

if (isDigit(formula.at(i)))

{

res *= 10;

res += (formula.at(i) - '0'); //получаем из символа соответствующую цифру

}

else break;

}

return res == 0 ? 1 : res; //0 - если перед формулой нет множителя, тогда он должен быть 1

}

void getContent(string formula, int multiplier, map<string, int> &content)

{

if (formula.find('(') != string::npos) //если есть скобки

{

int begin = formula.find('(') + 1; //первый символ внутри скобок

int end;

int bracketCounter = 1;

for (int i = begin; true; i++)

{

if (formula.at(i) == '(')

{

bracketCounter ++;

}

else if (formula.at(i) == ')')

{

bracketCounter--;

if (bracketCounter == 0)

{

end = i; //находим соответствующую закрывающую скобку

break;

}

int newMultiplier = multiplier;

int afterEnd = end + 1;

int backCoefficient = 0; //вычисляем коэффициент за скобочным выражением

for (int i = 1; true; i++)

{

if (end + i != formula.length() && isDigit(formula.at(end + i))) //пока есть числа за закрывающей скобкой, обновляем значение заднего коэффициента

{

backCoefficient *= 10;

backCoefficient += (formula.at(end + i) - '0');

afterEnd++;

}

else

{

if (backCoefficient == 0) //если чисел после закрывающей скобки нет, коэффициент равен 1

{

backCoefficient++;

}

newMultiplier *= backCoefficient; //вычисляем новое значение множителя для выражения внутри скобок

break;

}

if (begin != 1)

{

getContent(formula.substr(0, begin - 1), multiplier, content);

}

getContent(formula.substr(begin, end - begin), newMultiplier, content);

if (afterEnd < formula.length())

{

getContent(formula.substr(afterEnd), multiplier, content);

}

else //если скобок нет

{

string name = "";

string coefficient = "";

for (char c : formula)

{

if (isDigit(c))

{

coefficient += c;

}

else if (isLowerCaseLetter(c))

{

name += c;

}

else if (isUpperCaseLetter(c))

{

if (name.empty())

{

name += c;

}

else

{

if (coefficient.empty())

{

coefficient = "1";

}

update(content, name, multiplier * stoi(coefficient));

name.clear();

name += c;

coefficient = "";

}

if (!name.empty())

{

if (coefficient.empty())

{

coefficient = "1";

}

update(content, name, multiplier * stoi(coefficient));

}

void process(vector<string> subformulas, map<string, int> &content)

{

for (string subformula : subformulas) //для каждой подформулы:

{

int multiplier = getMultiplier(subformula); //вычисляем множитель перед ней

if (multiplier != 1) //если множитель записан явно

{

getContent(subformula.substr(floor(log10(multiplier)+1)), multiplier, content); //передаем в функцию подформулу, начиная с первого символа, не относящегося к переднему множителю

}

else

{

getContent(subformula, multiplier, content); //иначе передаем подформулу целиком

}

int main()

{

string mainFormula;

vector<string> mainSubformulas;

map<string, int> mainContent;

cin >> mainFormula;

split(mainFormula, mainSubformulas);

process(mainSubformulas, mainContent);

int n;

cin >> n;

string formulaToCompare;

vector<string> subformulasToCompare;

map<string, int> contentToCompare;

for (int i = 0; i < n; i++)

{

subformulasToCompare.clear(); //

contentToCompare.clear();

cin >> formulaToCompare;

split(formulaToCompare, subformulasToCompare);

process(subformulasToCompare, contentToCompare);

cout << mainFormula << (mainContent == contentToCompare ? "==" : "!=") << formulaToCompare << endl;

}

return 0;

}

Ссылки

Засчитанное решение на e-olymp.

Код на ideaone.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

e-olymp 1072. Химические реакции

Related Images:

Понравилось это:

Похожее

One thought on “e-olymp 1072. Химические реакции”

Добавить комментарий Отменить ответ

Related Images:

Поделиться ссылкой:

Понравилось это:

Похожее

One thought on “e-olymp 1072. Химические реакции”

Добавить комментарий Отменить ответ