Химические реакции

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

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

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

Формально, в BNF-подобной нотации: - <formula> ::= [<number>]<sequence>'+'[<number>]<sequence> - <sequence> ::= <element>[<number>]<element>[<number>] - <element> ::= <atom> | '(' <sequence> ')' - <atom> ::= <uppercase>[<lowercase>] - <uppercase> ::= 'A'..'Z' - <lowercase> ::= 'a'..'z' - <number> ::= '1'..'9''0'..'9'

Химический элемент учитывается как встречающийся $X$ раз в формуле, где $X$ — сумма всех вхождений, умноженная на соответствующие множители. Например, в формуле

C2H5OH+3O2+3(SiO2)

получаем: - C встречается $2$ раза, - H встречается $6$ раз (5+1), - O встречается $13$ раз (1+3\times2+3\times2), - Si встречается $3$ раза.

Все явно заданные множители в формуле — это положительные целые числа не менее $2$, и по умолчанию равны $1$. Каждая формула имеет длину не более $100$ символов, и ни один элемент не встречается в какой-либо формуле больше $10000$ раз.