<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>