Created
April 20, 2016 23:57
-
-
Save inakianduaga/e4d7fdce06d2bc1e56fd93d1c1137f62 to your computer and use it in GitHub Desktop.
Coursera Scala Functional Programming 1st Week balance brackets
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Criteria: Every closing parenthesis ) must have a unique opening ( parenthesis before it | |
* | |
* For every closing parenthesis, we search for the first opening parenthesis and remove it, and keep going | |
*/ | |
def balance(chars: List[Char]): Boolean = | |
(chars.indexOf(')'), chars.indexOf('(')) match { | |
case (leftMostClosing, leftMostOpening) if leftMostClosing == -1 && leftMostOpening != -1 => false // no closing / some opening => fail | |
case (leftMostClosing, leftMostOpening) if leftMostClosing == -1 && leftMostOpening == -1 => true // no closing or opening => ok | |
case (leftMostClosing, leftMostOpening) if leftMostClosing != 1 && leftMostOpening == -1 => false // closing but no opening => fail | |
case (leftMostClosing, leftMostOpening) if leftMostClosing != -1 && leftMostOpening != -1 // first closing before first opening | |
&& leftMostClosing < leftMostOpening => false | |
case (leftMostClosing, leftMostOpening) => balance( // first closing after first opening => strip them and recurse | |
chars | |
.zipWithIndex | |
.filter(tuple => tuple._2 != leftMostClosing && tuple._2 != leftMostOpening) | |
.map(tuple => tuple._1) | |
) | |
} |
In the end it looks like your solution, the generalization to a list of symbols is trivial
/**
* Determine if the string has balanced symbols
*/
def balancePair(chars: List[Char], pair: (Char, Char)): Boolean =
(chars.indexOf(pair._1), chars.indexOf(pair._2)) match {
case (-1, -1) => true // no closing or opening
case (-1, left) => false // no closing / some opening
case (right, -1) => false // closing but no opening
case (right, left) =>
if
(right != -1 && left != -1 && right < left) false // first closing before first opening
else
balancePair( // first closing after first opening => strip them and recurse
chars
.zipWithIndex
.filter(tuple => tuple._2 != right && tuple._2 != left)
.map(_._1),
pair
)
}
/**
* Determine if the string is balanced against a list of symbols
*/
def balancePairs(chars: List[Char], pairs: List[(Char, Char)]): Boolean = !pairs.map(balancePair(chars, _)).exists(!_)
@inakianduaga now go for the "nested is allowed" version :-)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@inakianduaga balanced in the traditional sense (i.e nested parenthesis are allowed)?
* Criteria: Every closing parenthesis ) must have a unique opening ( parenthesis before it
confuses me a bit. It seems the nested parenthesis are not allowed.In any case, for the solution listed in this gist, I'd argue that the pattern matching eloquence is lost due to the usage of
if
s to express the conditions. Always pattern match from most specific to least (this is the case also for tradicionalif
-else if
-else
nests).Might be that your approach is the usual in "official"
scala
style, but something like the following is way less noisy and (I believe) has the same meaning:The rest of the comment goes for "nested parenthesis are allowed", which is what I thought at the beginning
It's still not the most flexible solution. In imperative style this is always done with a mutable stack (push on open, pop on close and compare) and a loop. I'd suggest:
That'd be my approach to understand the whole thing better :-) .