The Dyck Language Correction Problem Given a word $w$ over $\{ [, ] \}$, the alphabet of the two square brackets, the Dyck correction problem is to find the shortest sequence of edit operations that would make $w$ a Dyck word, i.e., a word in which the squared brackets are balanced.
I can imagine a few practical applications, but my bibliography search yielded nothing. It looks like dynamic programming though. Any ideas?
The generalized problem, concerning Dyck($s$), for $s$ distinct pairs of parenthesis, was studied by Barna Saha in a paper entitled The Dyck Language Edit Distance Problem in Near-linear Time
B. Saha, &quot;The Dyck Language Edit Distance Problem in Near-Linear Time,&quot; 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, Philadelphia, PA, USA, 2014, pp. 611-620, doi: 10.1109/FOCS.2014.71.
Indeed, the problem is easy for $s=1$. For $s\ge2$ the exact complexity is not known. The classical techniques for correcting context-free languages are $O(sn^3)$ (Valiant 1975). On the other hand, the usual string editing problem which can be solved in quadratic time can be reduced to Dyck($s$).
Saha's result gives a nearly linear time algorithm that returns an approximation of the true edit distance. I am not sure whether this algorithm can produce the edit sequence.