Flow Graph Complexity

Soohwan leads the International Committee for Program Complexity (ICPC), and the main job of the committee is measuring the complexity of program code. One well known representation of a program is the control flow graph, where nodes are program constructs and edges are the possible flows of control. Cyclomatic complexity is a popular way to measure the complexity of a flow graph. For the digraph $G(V, E)$ that represents a flow graph, the cyclomatic complexity is $C(G) = |E| - |V| + 2$. For the flow graphs $G_1$ and $G_2$ in Figure C.1, both complexities are 3 ($C(G_1) = C(G_2) = 9 - 8 + 2 = 3$).

Figure C.1: two flow graphs, $G_1$ (a) and $G_2$ (b)

In Figure C.1 the labels B, L, and S give the node types: B for a branch, L for a loop, and S for a simple statement. A branch node B adds one forward edge that skips one or more statements. A loop node L is the target of an incoming backward edge, and it also adds a forward edge that leaves the loop. The dots that mark the closing points of loops and branches are nodes too.

One critique of cyclomatic complexity is that a backward edge added by a loop weighs the same as a forward edge. Soohwan therefore devised a measure that puts more weight on backward edges. He split the edges into two disjoint sets, $E_F$ for the forward edges and $E_B$ for the backward ones ($E = E_F \cup E_B$ and $E_F \cap E_B = \emptyset$), and defined a new measure, the flow graph complexity, as $C_M(G) = |E_F| + W \times |E_B| - |V| + 2$ for a constant backward edge weight $W$. Soohwan wants to validate this new measure.

Help Soohwan by writing a program that computes the new complexity of a given flow graph. To keep things simple, only pretest loops (while loops in C) and only one way branches (if statements without an else clause) appear. Under that assumption a flow graph is written as a string of node types:

• L for a loop node,
• B for a branch node, and
• S for a simple statement node.

L and B are each followed by the string of their sub-structure, enclosed in one pair of parentheses. The closing points are represented by the parentheses themselves. Node representations in a sequence are separated by commas. With this notation the graphs in Figure C.1 are written as follows:

• $G_1$: S,L(B(S)),S,S
• $G_2$: S,L(L(S)),S,S

With the weight $W = 5$ the new complexities are $C_M(G_1) = |E_F| + W \times |E_B| - |V| + 2 = 8 + 5 \times 1 - 8 + 2 = 7$ and $C_M(G_2) = |E_F| + W \times |E_B| - |V| + 2 = 7 + 5 \times 2 - 8 + 2 = 11$.

The graph denoted by a string is exactly this. A simple statement S is one node, and that node is both its entry and its exit. A branch B with sub-structure X consists of a branch node and a closing node. Its three edges are the forward edge from the branch node to the entry of X, the forward edge from the exit of X to the closing node, and the forward edge from the branch node to the closing node. Its entry is the branch node and its exit is the closing node. A loop L with sub-structure X also consists of a loop node and a closing node. Its three edges are the forward edge from the loop node to the entry of X, the forward edge from the exit of X to the closing node, and the backward edge from the closing node to the loop node. Its entry and its exit are both the loop node, so the forward edge that leaves the loop starts at the loop node. When items follow one another with commas, one forward edge runs from the exit of each item to the entry of the next one. The program as a whole has no separate start node and no separate end node.

Your program reads from standard input. The first line contains one integer $W$ ($1 < W \le 27$), the weight of a backward edge. The next line contains the string representation $P$ of the flow graph. The length of $P$ is less than 70,000. The string $P$ consists of uppercase letters and punctuation symbols. To make the representation easy to read, $P$ may contain spaces, which are ignored. A pair of brackets [ and ] may be used instead of a pair of parentheses, and an opening symbol must be closed by the same kind of symbol. $P$ may wrongly contain other punctuation symbols such as a colon (:), a semicolon (;), or a period (.), and your program must detect them as invalid symbols. The string $P$ is invalid if (1) the parentheses and the brackets are unmatched, (2) it contains punctuation symbols other than parentheses, brackets, and commas, (3) punctuation symbols are added or omitted wrongly, as in S,,S or SS or B,(S), or (4) it contains a node type other than S, L, or B. A valid graph contains at least one node.

Your program writes to standard output. Print exactly one line. The line contains the flow graph complexity $C_M(G)$ of the graph $G$ that $P$ represents. If the string $P$ is invalid, print -1 instead.