Programming assignment A4M33PAL

Task: Acyclic Isomers

In chemistry, isomers (from Greek ἰσομερής, isomerès; isos = "equal", méros = "part") are molecules that have the same molecular formula but different structural formulæ.

A molecule is an electrically neutral group of two or more atoms held together by covalent chemical bonds.

A covalent bond is a chemical bond that is formed when two atoms share electrons.

A molecular formula indicates the simple numbers of each type of atom (chemical element) in a molecule of a molecular substance. For example C6H12O6 is a molecule with six atoms of carbon, twelve atoms of hydrogen, and six atoms of oxygen.

Two molecules A and B have different structural formulae if there does not exist a bijection f from a set of atoms in A to a set of atoms in B such that (∀xA) (∀yB)(∀k∈{1,2,3}): ( (x and y have k-electron chemical bond) ⇔ ( (f(x) and f(y) have k-electron chemical bond) & (f(x) is the same chemical element as x) & (f(y) is the same chemical element as y) ) ).

An n-electron chemical bond is covalent bond when two atoms share n pairs of electrons. A 1-electron chemical bond (single bond) is formed when 1 pair of electrons is shared; a 2-electron chemical bond (double bond) is formed when 2 pairs of electrons are shared; and a 3-electron chemical bond (triple bond) is formed when 3 pairs of electrons are shared.

In chemistry, a cyclic molecule is a molecule in which a series of atoms is connected (by chemical bonds) to form a loop or ring. An acyclic molecule is a molecule which is not cyclic.

The Input

The input is always only one line containing a molecular formula.

The molecular formula has the following form. It is a nonempty sequence of pairs where every pair begins with one up-case letter for chemical element and it continues with positive integer number representing its frequency of occurrence in a molecule.

You can assume, that this formula can be composed from the following chemical elements only: carbon (C), hydrogen (H), oxygen (O), nitrogen (N).

You can also assume, that the number of all atoms in the molecular formula does not exceed 100.

Please note, that carbon has exactly four electrons in all its chemical bonds, hydrogen has exactly one electron in its chemical bond, oxygen has exactly two electrons in all its chemical bonds, and nitrogen has exactly three electrons in all its chemical bonds.

The Output

The output is always only one line with one number that represents the number of all acyclic isomers of the input molecular formula.

Example 1:

Input:

C4H8

Output:

3

Isomers:

For your convenience we add structural formulæ of all possible acyclic isomers.

    H   H H
    |   | |
    C=C-C-C-H
    | | | |
    H H H H
    H     H
    |     |
  H-C-C=C-C-H
    | | | |
    H H H H
        H
        |
      H-C-H H
        |   |
  H-C = C - C-H
    |       |
    H       H 

Example 2:

Input:

C2N2O2H2

Output:

67

Example 3:

Input:

C3H4O1

Output:

6

Isomers:

For your convenience we add structural formulæ of all possible acyclic isomers.

    H H H
    | | |
    C=C-C=O
    |
    H
    H   H
    |   |
    C=C=C-O-H
    |
    H
   H H
   | |
 H-C-C=C=O
   |
   H
       H
       |
 H-C≡C-C-O-H
       |
       H
         H
         |
 H-O-C≡C-C-H
         |
         H
         H
         |
 H-C≡C-O-C-H
         |
         H