화학자의 수학

보통 고등학교 화학 시간에는 화학 반응식을 배운다. 이 식은 다음과 같이 생겼다.

(1) 2H2 + O2 → 2H2O(2) Ca(OH)2 + CO2 → CaCO3 + H2O(3) N2 + 3H2 → 2NH3

위의 식 (1)~(3)은 모두 좌변과 우변의 균형이 맞추어져 있다.  하지만, 아래 반응식은 그렇지 않다.

(4) Al + O2 → Al2O3(5) C3H8 + O2 → CO2 + H2O

모든 화학 반응식은 질량 보존의 법칙을 지켜야 한다. 즉, 각 원소(H, O, Ca, Al, ...)의 개수는 화학 반응으로 변하지 않아야 한다. 따라서, 좌변과 우변에 분자의 개수를 맞추어 주어아 한다.

(6) 4Al + 3O2 → 2Al2O3(7) C3H8 + 5O2 → 3CO2 + 4H2O

반응식 (6)의 계수는 왼쪽부터 오른쪽까지 (4,3,2)이고, 반응식 (7)의 계수는 (1,5,3,4)이다. 계수가 1인경우에는 생략가능하다.

올바른 화학 반응식의 계수는 다음과 같은 조건을 만족한다.

1. 계수는 모두 양의 정수이다.
2. 계수는 서로소이다. 즉, 계수의 최대공약수는 1이다.
3. 모든 원소의 좌변의 양과 우변의 양은 같아야 한다.

화학 반응식이 위의 세가지 조건을 만족하는 경우에는 올바른 화학 반응식이라고 한다. 화학에서 실제로 일어날 수 없는 반응이나 존재하지 않는 분자가 등장한다고 해도, 이 문제에서는 올바른 화학 반응식이다. (H2 → H2도 올바른 반응식이다)

조건 1과 3(2는 필수는 아니다)을 만족하는 화학 반응식은 균형 반응식이라고 부른다.

화학 반응식 4와 5같이 계수가 없는 화학 반응식이 주어졌을 때, 계수를 올바르게 구하는 프로그램을 작성하시오.

모든 올바른 화학 반응식의 계수가 유일하게 결정되는 것은 아니다. 예를 들어, H2O와 NH3를 생성하는 반응식이 다음과 같다고 하자.

xH2 + yO2 + zN2 + uH2 → vH2O + wNH3

이 경우에 (x,y,z,u,v,w) = (2,1,1,3,2,2)가 답이 된다. 하지만, (4,2,1,3,4,2)와 (4,2,3,9,4,6)도 올바른 정답이 된다. 하지만, 이 문제에서 주어지는 모든 화학 반응식의 계수는 유일하게 결정된다.

입력은 여러 개의 계수가 없는 화학 반응식으로 이루어져 있다.

화학 반응식은 아래와 같이 BNF로 나타낼 수 있다.

<chemical_equation> ::= <molecule_sequence> "->" <molecule_sequence><molecule_sequence> ::= <molecule> | <molecule> "+" <molecule_sequence>         <molecule> ::= <group> | <group> <molecule>            <group> ::= <unit_group> | <unit_group> <number>       <unit_group> ::= <chemical_element> | "(" <molecule> ")" <chemical_element> ::= <uppercase_letter>                      | <uppercase_letter> <lowercase_letter> <uppercase_letter> ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I"                      | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R"                      | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" <lowercase_letter> ::= "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i"                      | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r"                      | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"           <number> ::= <non_zero_digit>                      | <non_zero_digit> <digit>   <non_zero_digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"            <digit> ::= "0" | <non_zero_digit>            

모든 화학 반응식의 끝에는 .이 주어진다. 예를 들어, 다음과 같은 방정식이 있을 때

Ca(OH)2 + CO2 → CaCO3 + H2O

입력으로는 다음과 같이 주어진다.

Ca(OH)2+CO2->CaCO3+H2O.

모든 화학 반응식의 길이는 80자를 넘지 않으며, <number>는 10보다 작다. 괄호는 중첩해서 사용되지 않는다. 화학 반응식의 각 변은 최대 10개의 분자로 이루어져 있다. 또, 계수는 항상 40,000을 넘지 않는다.

입력의 마지막 줄에는 .이 하나 주어진다.

위의 설명 중 <chemical_element>에서 주어지는 화학 원소는 존재하지 않는 원소나 아직 발견되지 않는 원소가 주어질 수도 있다. 또, 우누녹튬(Uuo, 118번)과 같이 원소가 알파벳 세글자인 경우도 주어지지 않는다.

각각의 화학 방정식에 대해서, 그 방정식을 올바르게 만드는 계수를 공백으로 구분하여 출력한다.