<html><head></head><body class="ApplePlainTextBody" dir="auto" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><blockquote type="cite">On 22/03/2017, at 5:53 AM, Michael Litchard <litchard.michael@gmail.com> wrote:<br><br>I'm prepping for a coding interview, and am examining the task of correcting unbalanced parentheses.<br></blockquote><br>Where is that task specified?<br><br>Back when the CWI in Amsterdam were working on an Algol 68<br>compiler, they had a technical report that looked at bracket<br>repair.  They had to deal with multiple kinds of brackets:<br>(-) [-] begin-end if-fi do-od case-esac.  It sounds as though<br>you don't have that problem, but it's still not clear what<br>you are supposed to do.  Given<br>  "(()"<br>is the correction "(())" or "()" or something else?  Given<br>  ")"<br>is the correction "() or ""?  How do you decide?<br><br><blockquote type="cite">The finger tree seems to be the right  data structure.<br></blockquote><br>Why?<br><br>Suppose we adopt the rules<br> - right parenthesis with no matching left: insert one<br> - n left parentheses with no match at the end: insert n rights<br><br>repair :: String -> String<br>repair ps = loop ps 0<br>  where loop []       n = map (\_ -> ')') [1..n]<br>        loop ('(':ps) n = '('   : loop ps (n+1)<br>        loop (')':ps) 0 = "()" ++ loop ps 0<br>        loop (')':ps) n = ')'   : loop ps (n-1)<br>        loop (x  :ps) n = x     : loop ps n<br><br>*Main> repair "(()"<br>"(())"<br>*Main> repair ")"<br>"()"<br>*Main> repair "))("<br>"()()()"                -- you want (())()<br>*Main> repair ")))"<br>"()()()"                -- you want ((()))<br><br>A rule of the form<br>  given a block of R ")" characters<br>  when the "(" stack is L deep:<br>  insert max(R-L,0) "(" characters<br>  copy the block of R ")" characters<br>  the "(" stack is now max(L-R,0) deep.<br>would produce the output you show without requiring any<br>complex data structure.<br><br>So what _is_ the specification?<br><br></body></html>