Решение задачи "Химические реакции" с Меньшиков

Без пояснения Просмотров: 21

Билл преподаёт химию в школе, он подготовил несколько тестов для учеников. Каждый тест состоит из химической формулы и нескольких возможных результатов реакции. Среди этих результатов ученики должны выбрать правильный. Билл хочет убедиться в том, что, вводя свои тесты в компьютер, он не допустил опечаток, благодаря которым ученики могли бы отбросить неверные ответы, просто подсчитав число химических элементов в левой и правой частях уравнения (в правильном уравнении химической реакции должно соблюдаться равенство).

Ваша задача - написать программу, которая поможет Биллу. Программа должна прочитать описание теста, состоящее из заданной левой части уравнения и нескольких возможных правых частей, и определить, равно ли количество химических элементов в каждой предложенной правой части уравнения количеству химических элементов в заданной левой части.

Билл формализовал задачу. И левая, и правая части уравнения представлены строкой символов без пробелов, состоящей из одной или более химических последовательностей, разделённых знаком плюс. Каждая последовательность имеет необязательный предшествующий целый множитель, относящийся ко всей последовательности, и несколько элементов. Каждый элемент может сопровождаться необязательным целым множителем, относящимся к нему. Элемент в этом уравнении может быть или отдельным химическим элементом, или целой последовательностью в круглых скобках. Каждый отдельный химический элемент представлен или одной прописной буквой, или прописной буквой, сопровождаемой строчной.

Ещё более формально, используя нотацию, аналогичную форме Бэкуса-Наура, можно написать:

<формула> ::= [<число>] <последовательность> {"+" [<число>] <последовательность>}
<последовательность> ::= <элемент> [<число>] {<элемент> [<число>]}
<элемент> ::= <химический элемент> | "(" <последовательность> ")"
<химический элемент> ::= <прописная буква> [<строчная буква>]
<прописная буква> ::= "A".."Z"
<строчная буква> ::= "a".."z"
<число> ::= "1".."9" {"0".."9"}
Будем говорить, что каждый отдельный химический элемент встречается в формуле всего X раз, если X - сумма всех различных вхождений этого химического элемента, умноженных на все числа, относящиеся к ним. Например, в формуле C2H5OH+3O2+3(SiO2)

C встречается всего 2 раза;
H встречается всего 6 раз (5 + 1);
O встречается всего 13 раз; (1 + 3 * 2 + 3 * 2);
Si встречается всего 3 раза.
Все множители в формулах - целые числа не меньше 2, если заданы явно, или равны 1 - по умолчанию.

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <string.h>
using namespace std;
 
int n;
typedef map<string,int> form;
 
void ReadSequence(char* &pos, int number, form& formula);
 
inline bool _isEnd(const char* pos)
{
    return !*pos;
}
inline bool _isDigit(const char* pos)
{
    //<число> ::= "1".."9" {"0".."9"}
    if (_isEnd(pos)) return false;
    return '0' <= *pos && *pos <= '9';
}
inline bool _isUpLetter(const char* pos)
{
    //<прописная буква> ::= "A".."Z"
    if (_isEnd(pos)) return false;
    return 'A'<= *pos && *pos <='Z';
}
inline bool _isLwLetter(const char* pos)
{
    //<строчная буква> ::= "a".."z"
    if (_isEnd(pos)) return false;
    return 'a'<= *pos && *pos <='z';
}
inline bool _isChemElemBegin(const char* pos)
{
    if (_isEnd(pos)) return false;
    return _isUpLetter(pos);
}
inline bool _isElemBegin(const char* pos)
{
    if (_isEnd(pos)) return false;
    return _isChemElemBegin(pos) || *pos == '(';
}
inline bool _isSeqBegin(const char* pos)
{
    if (_isEnd(pos)) return false;
    return _isElemBegin(pos);
}
inline bool _isPlusSeq(const char* pos)
{
    if (_isEnd(pos)) return false;
    return *pos == '+';
}
void ReadNumber(char* &pos, int &number)
{
    number = number*10 + (*pos - '0');
    pos++;
    if (!_isEnd(pos) && _isDigit(pos))
        ReadNumber(pos,number);
}
void ReadChemElement(char* &pos, string &chemElement)
{
    //<химический элемент> ::= <прописная буква> [<строчная буква>]
    chemElement += *pos++;
    if (_isLwLetter(pos))
        chemElement += *pos++;
}
void ReadElement(char* &pos, int number, form &formula)
{
    //<элемент> ::= <химический элемент> | "(" <последовательность> ")"
    if (*pos == '(')
    {
        pos++;
        ReadSequence(pos, number, formula);
        pos++;
    }
    else
    {
        string chemElement = "";
        ReadChemElement(pos, chemElement);
        formula[chemElement] += 1;
    }
}
void ReadSequence(char* &pos, int number, form& totalFormula)
{
    //<последовательность> ::= <элемент> [<число>] {<элемент> [<число>]}
    form localFormula;
    while (_isElemBegin(pos)) {
        localFormula.clear();
        ReadElement(pos, number, localFormula);
        int mul = 1;
        if (_isDigit(pos)) {
            mul = 0;
            ReadNumber(pos, mul);
        }
 
        form::iterator it = localFormula.begin();
        for (it; it!= localFormula.end();it++)
            totalFormula[it->first] += it->second * mul;
    }
}
void ReadFormula(char* &pos, form &formula)
{
    //<формула> ::= [<число>] <последовательность> {"+" [<число>] <последовательность>}
    if (_isEnd(pos)) return;
    do
    {
        int number = 1;
        if (_isDigit(pos)){
            number = 0;
            ReadNumber(pos,number);
        }
        form seqFormula;
        if (_isSeqBegin(pos))
            ReadSequence(pos,number,seqFormula);
 
        form::iterator it = seqFormula.begin();
        for (it; it != seqFormula.end(); it++)
            formula[it->first] += it->second * number;
    }
    while (_isPlusSeq(pos++));
}
void ReadFormulaString(string &strFormula, form &formula)
{
    cin>>strFormula;
    char* buf = new char[strFormula.size()+1]; // +1 на нуль символ
    strcpy(buf,strFormula.c_str());
   
    ReadFormula(buf,formula);
 
    buf -= strFormula.size() + 1;
    delete [] buf;
}
void input()
{
    string initStrFormula = "";
    form initFormula;
    ReadFormulaString(initStrFormula, initFormula);
   
    cin>>n;
    for (int i=0;i<n;i++)
    {
        form curFormula;
        string curStrFormula;
        ReadFormulaString(curStrFormula, curFormula);
 
        cout<<initStrFormula;
        if (curFormula == initFormula)
            cout<<"==";
        else
            cout<<"!=";
        cout<<curStrFormula<<endl;
    }
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    return 0;
}

Решение задачи "Химические реакции" с Меньшиков

Без пояснения Просмотров: 21

Код

Автор: Администратор

Комментарии

Решение задачи "Химические реакции" с Меньшиков

Без пояснения Просмотров: 21

Код Скопировать код

Автор: Администратор

Комментарии

Код