On 22/03/2017, at 5:53 AM, Michael Litchard <litchard.michael@gmail.com> wrote:

I'm prepping for a coding interview, and am examining the task of correcting unbalanced parentheses.

Where is that task specified?

Back when the CWI in Amsterdam were working on an Algol 68
compiler, they had a technical report that looked at bracket
repair. They had to deal with multiple kinds of brackets:
(-) [-] begin-end if-fi do-od case-esac. It sounds as though
you don't have that problem, but it's still not clear what
you are supposed to do. Given
"(()"
is the correction "(())" or "()" or something else? Given
")"
is the correction "() or ""? How do you decide?

The finger tree seems to be the right data structure.

Why?

Suppose we adopt the rules
- right parenthesis with no matching left: insert one
- n left parentheses with no match at the end: insert n rights

repair :: String -> String
repair ps = loop ps 0
where loop []       n = map (\_ -> ')') [1..n]
       loop ('(':ps) n = '('   : loop ps (n+1)
       loop (')':ps) 0 = "()" ++ loop ps 0
       loop (')':ps) n = ')'   : loop ps (n-1)
       loop (x :ps) n = x     : loop ps n

*Main> repair "(()"
"(())"
*Main> repair ")"
"()"
*Main> repair "))("
"()()()"                -- you want (())()
*Main> repair ")))"
"()()()"                -- you want ((()))

A rule of the form
given a block of R ")" characters
when the "(" stack is L deep:
insert max(R-L,0) "(" characters
copy the block of R ")" characters
the "(" stack is now max(L-R,0) deep.
would produce the output you show without requiring any
complex data structure.

So what _is_ the specification?