The Hex-Weave of the Brannagh Coven

The witches of the Brannagh Coven write their curses on strips of rowan bark: the true names of bound spirits, joined by binding-marks. Before a hexbreaker can unpick a curse, they must know exactly which spirits each mark holds together. The coven's stolen grimoire lists every mark with a strength and a direction. The Hexbreakers' Lodge of Bitwick pays well for a reader that makes every binding on a strip explicit, and that refuses strips the coven botched.

Write hexWeave(chant, binds), which returns the chant with every binding made explicit, or the string "broken" if the chant is malformed.

Arguments - chant: a string. - binds: an object (dict) mapping each mark, a single character, to a two-element list [strength, direction]. The strength is an integer, which may be zero or negative. The direction is one of "left", "right" or "none". A mark is never a lowercase letter, a space, or a parenthesis. All marks that share a strength also share a direction.

Reading the chant. Scan it from left to right: - A space is ignored, except that it separates names. - A name is a maximal run of lowercase letters a-z. - ( and ) are parentheses. - A character that is a key of binds is a mark. - Any other character makes the chant broken. This includes uppercase letters, digits, and mark-like characters that are not keys of binds.

Shape. The sequence of names, marks and parentheses must match this grammar exactly, using every item: - chant := group - group := operand, followed by zero or more pairs of (mark, operand) - operand := a name, or ( group )

Anything else is broken. For example: an empty chant, two names side by side, a mark at the start or end, two marks in a row, empty parentheses, or unbalanced parentheses.

Grouping 1. Parentheses group first. 2. A mark of higher strength binds tighter than one of lower strength. 3. A run of marks of equal strength with direction "left" groups from the left: a-b-c means ((a-b)-c). With direction "right", it groups from the right: a^b^c means (a^(b^c)). 4. Marks of a strength whose direction is "none" may not be grouped against one another without parentheses. The chant is broken if, however it were grouped, some such mark would have as its left or right operand a binding made by a mark of the same strength, where that binding is not wrapped in its own parentheses in the chant. This rule still applies when other marks stand between them.

Return value. Write a name as itself. Write a binding of left operand L and right operand R by mark m as ( + L + m + R + ), with no spaces anywhere. The chant's own parentheses do not appear in the output; only the brackets around each binding do. A chant that is a single name, even if wrapped in parentheses, returns just that name. A malformed chant returns "broken".