Code Review Request - Unbalanced Parenthesis correction

14 messages
Open this post in threaded view
|

Code Review Request - Unbalanced Parenthesis correction

 I'm prepping for a coding interview, and am examining the task of correcting unbalanced parentheses. The finger tree seems to be the right data structure. As a proof of concept I've used `Data.Sequence` to test my idea. If this is the right direction to go, I'll write more specialized finger tree code. The code works on the few test cases I have tried. Feedback appreciated. ``````{-# LANGUAGE ViewPatterns #-} module Parenthesis where import BasicPrelude hiding (concat,null,empty) import Data.Sequence hiding (length) import Data.Foldable hiding (length,null) balanceParens :: String -> String balanceParens str = go str [] empty where go [] [] (null -> True) = [] go [] [] parens = Data.Foldable.toList parens go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(') go (')':xs) [] (null -> True) = go xs [] (fromList "()") go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(') go (')':xs) [] parens = go xs [] corrected where corrected = ('(' <| parens) |> ')' go (')':xs) (RP:debit) parens = go xs debit (parens |> ')') go (_:xs) debit parens = go xs debit parens go [] (RP:debit) parens = go [] debit (parens |> ')')`````` example: ``````balanceParens "))(" "(())()" balanceParens ")))" "((()))"`````` _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

 Hi Michael,Are there any strange constraints on the problem, such as the input string being 10s of GB long, or any particular correction strategy being required? Your code seems to add some parens to the start/end of the entire string to balance it, whereas I think I might have balanced "))(" to "()()()" given free reign. Is the goal efficiency or clarity or something else?From personal taste, I would recommend including a suite of automated tests alongside your implementation even if it is not explicitly requested. A quickcheck test asserting that the output is always balanced and that the input string is a substring of the output might be appropriate.On 21 March 2017 at 16:53, Michael Litchard wrote: I'm prepping for a coding interview, and am examining the task of correcting unbalanced parentheses. The finger tree seems to be the right data structure. As a proof of concept I've used `Data.Sequence` to test my idea. If this is the right direction to go, I'll write more specialized finger tree code. The code works on the few test cases I have tried. Feedback appreciated. ``````{-# LANGUAGE ViewPatterns #-} module Parenthesis where import BasicPrelude hiding (concat,null,empty) import Data.Sequence hiding (length) import Data.Foldable hiding (length,null) balanceParens :: String -> String balanceParens str = go str [] empty where go [] [] (null -> True) = [] go [] [] parens = Data.Foldable.toList parens go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(') go (')':xs) [] (null -> True) = go xs [] (fromList "()") go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(') go (')':xs) [] parens = go xs [] corrected where corrected = ('(' <| parens) |> ')' go (')':xs) (RP:debit) parens = go xs debit (parens |> ')') go (_:xs) debit parens = go xs debit parens go [] (RP:debit) parens = go [] debit (parens |> ')')`````` example: ``````balanceParens "))(" "(())()" balanceParens ")))" "((()))"`````` _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

 In reply to this post by Michael Litchard-2 Whether your algorithm is correct depends on how you are supposed to rebalance them.  My naive attempt gives very different results. bal :: String -> String bal = go 0   where     go :: Int -> String -> String     go 0 "" = ""     go n "" = replicate n ')'     go n ('(':xs) = '(' : (go (n + 1) xs)     go 0 (')':xs) = '(' : ')' : (go 0 xs)     go n (')':xs) = ')' : (go (n - 1) xs) bal "))(" "()()()" bal ")))" "()()()" On Tue, Mar 21, 2017 at 12:53 PM, Michael Litchard <[hidden email]> wrote: > I'm prepping for a coding interview, and am examining the task of correcting > unbalanced parentheses. The finger tree seems to be the right data > structure. As a proof of concept I've used Data.Sequence to test my idea. If > this is the right direction to go, I'll write more specialized finger tree > code. The code works on the few test cases I have tried. Feedback > appreciated. > > {-# LANGUAGE ViewPatterns #-} > module Parenthesis where > import BasicPrelude hiding (concat,null,empty) > > import Data.Sequence hiding (length) > import Data.Foldable hiding (length,null) > > balanceParens :: String -> String > balanceParens str = go str [] empty >   where >     go [] [] (null -> True) = [] >     go [] [] parens = Data.Foldable.toList parens >     go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(') >     go (')':xs) [] (null -> True) = go xs [] (fromList "()") >     go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(') >     go (')':xs) [] parens = go xs [] corrected >       where corrected = ('(' <| parens) |> ')' >     go (')':xs) (RP:debit) parens = go xs debit (parens |> ')') >     go (_:xs) debit parens = go xs debit parens >     go [] (RP:debit) parens = go [] debit (parens |> ')') > > example: > > balanceParens "))(" > "(())()" > balanceParens ")))" > "((()))" > > > _______________________________________________ > Haskell-Cafe mailing list > To (un)subscribe, modify options or view archives go to: > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe> Only members subscribed via the mailman list are allowed to post. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

 In reply to this post by David McBride On 03/21/2017 01:16 PM, David McBride wrote: > Whether your algorithm is correct depends on how you are supposed to > rebalance them.  My naive attempt gives very different results. > You guys are trying to hard. Here's an algorithm that meets the stated requirements:    balance _ = "" _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

 In reply to this post by Michael Litchard-2 Hi Michael, I think you're making your own task harder than necessary. For one thing, -XViewPatterns is nice, but in this case they hide some of the structure. Most importantly, they hide that all the special null-cases are actually unnecessary because the normal cases already cover them. I would further advise to use layout to reveal even more structure. That's especially useful when you later convert the explicit recursion into a fold. But even then, on a different level you're still working too hard: You're parsing the string and building/correcting the tree in one step. Why not create the tree, convert the tree, and then read out the tree in three steps? It's still the same complexity class but much easier to write and read. And once you are free to think of the tree manipulations on their own it might help recognize optimizations like those the solutions of other commenters use. That's not to say your modifications are useless. But the exploratory phase seems too early to apply them. Cheers, MarLinn On 2017-03-21 17:53, Michael Litchard wrote: I'm prepping for a coding interview, and am examining the task of correcting unbalanced parentheses. The finger tree seems to be the right data structure. As a proof of concept I've used `Data.Sequence` to test my idea. If this is the right direction to go, I'll write more specialized finger tree code. The code works on the few test cases I have tried. Feedback appreciated. ``````{-# LANGUAGE ViewPatterns #-} module Parenthesis where import BasicPrelude hiding (concat,null,empty) import Data.Sequence hiding (length) import Data.Foldable hiding (length,null) balanceParens :: String -> String balanceParens str = go str [] empty where go [] [] (null -> True) = [] go [] [] parens = Data.Foldable.toList parens go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(') go (')':xs) [] (null -> True) = go xs [] (fromList "()") go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(') go (')':xs) [] parens = go xs [] corrected where corrected = ('(' <| parens) |> ')' go (')':xs) (RP:debit) parens = go xs debit (parens |> ')') go (_:xs) debit parens = go xs debit parens go [] (RP:debit) parens = go [] debit (parens |> ')')`````` example: ``````balanceParens "))(" "(())()" balanceParens ")))" "((()))"`````` ```_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.``` _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

 In reply to this post by Michael Litchard-2 On 22/03/2017, at 5:53 AM, Michael Litchard <[hidden email]> 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 68compiler, they had a technical report that looked at bracketrepair.  They had to deal with multiple kinds of brackets:(-) [-] begin-end if-fi do-od case-esac.  It sounds as thoughyou don't have that problem, but it's still not clear whatyou 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 rightsrepair :: String -> Stringrepair 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 anycomplex data structure.So what _is_ the specification?_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|