Задачи
Химические реакции
Химические реакции
Билл преподает химию в школе, он подготовил несколько тестов для учеников. Каждый тест состоит из химической формулы и нескольких возможных результатов реакции. Среди этих результатов ученики должны выбрать правильный. Билл хочет убедиться в том, что вводя свои тесты в компьютер, он не допустил опечаток, благодаря которым ученики могли бы отбросить неверные ответы, просто подсчитав число химических элементов в левой и правой частях уравнения (в правильных уравнениях химической реакции должно соблюдаться равенство).
Ваша задача - написать программу, которая поможет Биллу. Программа должна прочитать описание теста, состоящее из левой части уравнения и нескольких возможных правых частей, и определить, равно ли количество химических элементов в каждой предложенной правой части уравнения количеству химических элементов в заданной левой части.
Билл формализировал задачу. И левая, и правая части уравнения представляется строкой символов без пробелов, состоящей из одной или более химических последовательностей, разделенных знаком плюс. Каждая последовательность имеет необязательный предшествующий целый множитель, относящийся ко всей последовательности, и несколько элементов. Каждый элемент может сопровождаться необязательным целым множителем, относящимся к нему. Элемент в этом уравнении может быть или отдельным химическим элементом, или целой последовательность в круглых скобках. Каждый отдельный химический элемент представлен или одной прописной буквой, или прописной буквой, сопровождаемой строчной.
Если более формально, используя нотацию, аналогичную форме Бэкуса-Наура, можно написать:
<формула>::=\[<число>\]<последовательность>\{"+"\[<число>\]<последовательность>\}
<последовательность>::=<элемент>\[<число>\]\{<элемент>\[<число>\]\}
<элемент>:=<химический элемент>|"("<последовательность>")"
<химический элемент>::=<прописная буква>\[<строчная буква>\]
<прописная буква>::="A".."Z"
<строчная буква>::="a".."z"
<число>::="1".."9"\{"0".."9"\}
Будем говорить, что каждый отдельный химический элемент встречается в формуле всего \textbf{X} раз, если \textbf{X} - сумма всех различных вхождений этого химического элемента, умноженных на все числа, относящиеся к ним. Например в формуле \textbf{C2H5OH+3O2+3(SiO2)}
\begin{itemize}
\item \textbf{C} встречается всего \textbf{2} раза;
\item \textbf{H} встречается всего (\textbf{5+1}) раз;
\item \textbf{O} встречается всего \textbf{13} раз (\textbf{1+3·2+3·2});
\item \textbf{Si} встречется всего \textbf{3} раза.
\end{itemize}
Все множители в формулах - целые числа не меньшие \textbf{2}, если заданы явно, или равны \textbf{1} - по умолчанию.
\InputFile
В первой строке находится формула - левая часть уравнения, во второй- одно число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10}) - количество рассматриваемых правых частей, в каждой из последующих \textbf{N} строк - одна формула - предполагаемая правая часть уравнения.
Длина формулы не превосходит \textbf{100} символов, каждый отдельный химический элемент встречается всего не более \textbf{10000} раз в каждой формуле.
\OutputFile
Для каждой из \textbf{N} заданных строк вывести одну строку вида
<\textbf{формула левой части}>==<\textbf{формула правой части}>
если общее количество вхождений каждого отдельного химического элемента в левую часть равно общему числу вхождений этого химического элемента в правую часть. В противном случае выведите:
<\textbf{формула левой части}>!=<\textbf{формула правой части}>
Здесь <\textbf{формула левой части}> должна быть заменена посимвольной копией формулы левой части, как она дана в первой строке входного файла, а <\textbf{формула правой части}> - замещена точной копией формулы правой части, как она дана во входном файле. В строках не должно быть пробелов.
Входные данные #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
Выходные данные #1
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