Skip to content

Instantly share code, notes, and snippets.

@f0ster
Last active Jul 24, 2018
Embed
What would you like to do?
verifying balanced parens with recursion
def balance(chars: List[Char]): Boolean = {
def balanced(chars: List[Char], currently_open_parens: Int): Boolean = {
if (chars.isEmpty) currently_open_parens == 0
else {
if(chars.head == '(') balanced(chars.tail, currently_open_parens+1)
else {
if(chars.head == ')' ) {
currently_open_parens > 0 && balanced(chars.tail, currently_open_parens-1)
} else balanced(chars.tail, currently_open_parens)
}
}
}
balanced(chars,0)
}
@lockwobr
Copy link

lockwobr commented Jul 24, 2018

another way to write that using match and tailrec

import scala.annotation.tailrec

def balance(s: String): Boolean ={
    @tailrec
    def balanced(s: List[Char], currently_open_parens: Int = 0): Boolean ={
      s match {
        case '(' :: tail => balanced(tail, currently_open_parens+1)
        case ')' :: tail if(currently_open_parens > 0) => balanced(tail, currently_open_parens-1)
        case _ if(s.nonEmpty) => balanced(s.tail, currently_open_parens)
        case _ => currently_open_parens == 0
      }
    }
    return balanced(s.toList)
  }

@f0ster
Copy link
Author

f0ster commented Jul 24, 2018

@lockwobr 🔥

@lockwobr
Copy link

lockwobr commented Jul 24, 2018

or another way to do it with no rec, but has a flaw

def balance(s: String): Boolean ={
    return s.toList.map(c => {
      c match {
        case '(' => 1
        case ')' => -1
        case _ => 0
      }
    }).sum == 0
  }

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment