Skip to content

Instantly share code, notes, and snippets.

@mepcotterell
Created February 28, 2012 02:39
Show Gist options
  • Save mepcotterell/1928805 to your computer and use it in GitHub Desktop.
Save mepcotterell/1928805 to your computer and use it in GitHub Desktop.
Balanced parentheses example.
object Parens extends App {
def balanced (input: String): Boolean = {
val stack = collection.mutable.Stack.empty[String]
import stack._
for (i <- input) i match {
case '(' => push("(")
case '[' => push("[")
case ')' => if (isEmpty) return false else if (pop() != "(") return false
case ']' => if (isEmpty) return false else if (pop() != "[") return false
} // for
true
} // balanced
def balanced2 (input: String): Boolean = {
if (input.length % 2 != 0) return false
var (p, ps, b, bs) = (0, 0, 0, 0)
for (i <- input) i match {
case '(' => { p +=1; ps = 0; if (bs > 0) bs += 1 }
case '[' => { b +=1; bs = 0; if (ps > 0) ps += 1 }
case ')' => { p -=1; ps += 1 + (if (bs > 0) bs else 0) }
case ']' => { b -=1; bs += 1 + (if (ps > 0) ps else 0) }
} // for
if ((p == 0) && (b == 0) && (bs + ps <= input.length)) true else false
} // balanced2
List("([][])",
"([()])",
"((()))",
"([)]()",
"())())") foreach {
e => {
println(e)
if (balanced2(e)) println(" is balanced!") else println(" is not balanced")
}
}
} // Parens
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment