The Host-Glyphs of the Tarnhollow Summoners

Commission of the Tarnhollow Summoners' Lodge. Before any expedition into the Greymarch calls up a host from the Tarnhollow binding-circle, the host is written out as a *host-glyph*: a string naming each creature to be called and how many. A miswritten glyph tears the circle. The Lodge pays a Warden to check every glyph and to tally the host it calls.

Write summonHost(glyph). glyph is a string. If the glyph is well-formed, return its canonical tally as a string. If it is malformed, return null (Python: None).

A well-formed glyph is a sequence of zero or more *terms*, written one after another with nothing between them: - A *term* is a *name* or a *group*, optionally followed by a *count*. - A *name* is one uppercase letter A-Z followed by zero or more lowercase letters a-z, read for as long as lowercase letters continue. For example, Imps is one name. - A *group* is one of two forms: - (, then a sequence of one or more terms, then ). - [, then a sequence of one or more terms, then ].

A group must close with the same kind of bracket that opened it. Groups may nest to any depth. - A *count* is one or more ASCII digits 0-9 with no leading zero. Its value is therefore at least 1. A term with no count has count 1.

The glyph is malformed if any of the following occurs: - Any other character appears, such as a space or other punctuation. - A lowercase letter or a digit appears where a term must begin. - A bracket is unmatched or mismatched. - A group is empty.

The empty string is well-formed and calls no creatures.

The tally. - A name with count k calls k of that creature. - A group with count k calls everything inside it k times over. - The same name may appear any number of times. Its totals add together.

The canonical tally lists every creature called. Each creature appears exactly once, written as its name immediately followed by its total. A total of 1 is written as the name alone.

The entries are joined with no separators and ordered as follows: 1. By total, descending, compared as numbers. 2. Creatures with equal totals in ascending character-code order of their names.

An empty glyph gives the empty string. Every total fits in a safe integer.