The Nested Phials of the Orrinvale Alembists

The Alembists of Orrinvale brew the warding-draughts carried by parties bound for the Hollowmere Barrows. Their formulae are written in a cramped notation of reagents and nested phials. Before a draught can be brewed at a field camp, its formula must be settled into plain form, with one entry per reagent and its total measure. Formulae copied in haste are sometimes corrupt, and a corrupt formula must be refused outright. The guild pays for a settler that never errs.

Write settleFormula(formula). It takes a string formula and returns a string.

The notation

• A reagent name is one uppercase letter A–Z followed by zero or more lowercase letters a–z. The name ends at the first character that is not a lowercase letter. So AshMoss is two reagents, Ash and Moss.
• A phial is ( followed by a formula followed by ), or [ followed by a formula followed by ]. A phial must close with the same kind of bracket that opened it. The formula inside a phial must be non-empty and valid, so (), [] and (()) are all corrupt.
• A count is a run of one or more digits 0–9 placed immediately after a reagent name or after a phial's closing bracket. All consecutive digits are read as one decimal number, and that number multiplies the item they follow. A count must not begin with 0, so 0 and 05 are corrupt. An explicit 1 is allowed. An item with no count has count 1.
• A formula is a sequence of zero or more items. Each item is a reagent name or a phial, and each item may be followed by a count. The empty string is a valid formula.

The formula is corrupt if it cannot be read entirely by these rules. Examples of corrupt input include:

• a closing bracket with no matching opener
• an unclosed phial
• a closer of the wrong kind
• a digit that does not follow a name or a phial
• a lowercase letter that does not continue a name
• any other character, including spaces

What to return

• If the formula is corrupt, return the string "INVALID".
• Otherwise, compute each reagent's total measure. For every occurrence of the reagent, multiply that occurrence's own count by the count of every phial enclosing it. The total measure is the sum of these products over all occurrences.
• Return a string listing each distinct reagent exactly once, in this order:
• by total measure, largest first;
• ties broken by name in ascending character-code order (so Ash comes before Ashen).
• Write each reagent as its name followed by its total in decimal with no leading zeros. When the total is exactly 1, write the name alone. Entries are concatenated with no separators.
• An empty formula settles to the empty string "".

All totals in the tests are below one billion.