Bernd is a high school student who has some problems in chemistry. In class he has to design chemical equations for some experiments they are doing, such as the combustion of heptane
C7H16 + 11O2 → 7CO2 + 8H2O
Since mathematics isn't exactly Bernd's strongest subject, he often has a hard time finding the exact ratios between the pro- and educts of the reaction. Since you are Bernd's tutor, it is your job to help him! Write a program, that calculates the amount of each substance needed to get a valid chemical equation.
The input is a chemical equation without amounts. In order to make this possible in pure ASCII, we write any subscriptions as ordinary numbers. Element names always start with a capital letter and may be followed by a minuscule. The molecules are separated with
+ signs, an ASCII-art arrow
-> is inserted between both sides of the equation:
The input is terminated with a newline and won't contain any spaces. If the input is invalid, your program may do whatever you like.
You may assume, that the input is never longer than
1024 characters. Your program may either read the input from standard input, from the first argument or in an implementation defined way at runtime if neither is possible.
The output of your program is the input equation augmented with extra numbers. The number of atoms for each element must be the same on both sides of the arrow. For the example above, a valid output is:
If the number for a molecule is
1, drop it. A number must always be a positive integer. Your program must yield numbers such that their sum is minimal. For instance, the following is illegal:
If there is no solution, print
instead. A sample input that has no solution is
C7H16+O2->CO2+H2O C7H16+11O2->7CO2+8H2O Al+Fe2O3->Fe+Al2O3 2Al+Fe2O3->2Fe+Al2O3 Pb->Au Nope!
This is code-golf, so shortest code wins!
Your program must terminate in reasonable time for all reasonable inputs