BOI 2005: SPOILER FOR "MAGIC PARENTHESIS"


A straightforward cubic (in N) Dynamic Programming solution can be
derived using the classical Cocke-Younger-Kasami (CYK) parsing
algorithm.

Let us first write a Contex Free Grammar (CFG) for "magic-balanced"
strings, where E stands for the empty string (usually denoted with
either epsilon or lambda):

S : E
  | ( S )
  | S S
  | ( A

A : S ]
  | ( A

Then eliminate the empty string E from the grammar as follows:

S : ( )
  | ( S )
  | S S
  | ( A

A : ]
  | S ]
  | ( A

Note that the task description precludes the whole input from being
empty, so we can omit the production S : E.

Then modify the grammar to the normal form required by CYK:

S : ( )
  | ( B
  | S S
  | ( A/R

A : S R
  | P A/R

B : S )

R : ]

The notation A/R means either of them. The new nonterminal R is used
for ']' in eliminating the unit production A : ]. This nonterminal is
useful below in organizing printing out the count C_i for the i:th
magic parenthesis ']'.

The algorithm parses the input with our CYK version. The first line of
the output tells whether this parsing succeeded or not.

If it succeeded, then it produced some parse tree T. The rest of the
output is printed with a preorder traversal of T as follows.

The nonterminal A is given the attribute

m = the number of '(':s that the rightmost R generated by this A must
match

denoted as A{m}. 

This attribute is evaluated top-down during the recursion over T as follows:

S : P A/R{1}		    initializes it 

A{m} : P A/R{m+1}	    increments it

A{m} : S R{m}		    passes it to the rightmost R

R{m} : ]		    prints it.