I'm working on some code to balance parenthesis, this question proved most useful for the algorithm.
I implemented it in my first language (PHP) but I'm learning Scala and trying to convert the code.
Here is my PHP code:
function balanced($string) {
return isBalanced($string, "");
}
function isBalanced($chars, $stack) {
if (!strlen($chars))
return empty($stack);
switch ($chars[0]) {
case '(':
// prepend stack with '(', move to next character
return isBalanced(substr($chars, 1), $chars[0] . $stack);
case ')':
// if '(' seen previously, shift stack, move to next character
return !empty($stack) && isBalanced(substr($chars, 1), substr($stack, 1));
default:
// do nothing to stack, move to next character
return isBalanced(substr($chars, 1), $stack);
}
}
I've test this, it works. However, when I convert it to Scala, it fails on balanced strings.
My Scala code:
object Main {
def balance(chars: List[Char]): Boolean = {
def balanced(chars: List[Char], stack: String): Boolean = {
if (chars.isEmpty)
stack.isEmpty
else if (chars.head == ')')
balanced(chars.tail, chars.head + stack)
else if (chars.head == '(')
!stack.isEmpty && balanced(chars.tail, stack.tail)
else
balanced(chars.tail, stack)
}
balanced(chars, "")
}
}
I appreciate this isn't the best Scala code but I'm just starting out. Some tests:
balance("(if (0) false (x))".toList) - fails
balance("profit and loss (P&L).\n(cashflow)".toList) - fails
balance(":)".toList) - passes
balance(")(()".toList) - passes
The PHP equivalent passes all these tests. What have I done wrong in my Scala implementation?
You have mixed up the cases for ( and ).
For what it's worth, here's a more idiomatic Scala implementation:
def balance(chars: List[Char]): Boolean = {
@tailrec def balanced(chars: List[Char], open: Int): Boolean =
chars match {
case Nil => open == 0
case '(' :: t => balanced(t, open + 1)
case ')' :: t => open > 0 && balanced(t, open - 1)
case _ :: t => balanced(t, open)
}
balanced(chars, 0)
}
Just for completeness, I found an even more terse 'scala-esque' implementation from another SO question:
def balance(chars: List[Char]): Boolean = chars.foldLeft(0){
case (0, ')') => return false
case (x, ')') => x - 1
case (x, '(') => x + 1
case (x, _ ) => x
} == 0
Same as Aaron Novstrup's answer but using 'if else'. I'm also attending the same course but we are taught upto if/else only so far.
def balance(chars: List[Char]): Boolean = {
def balanced(chars: List[Char], open: Int): Boolean =
if (chars.isEmpty) open == 0
else if (chars.head == '(') balanced(chars.tail, open + 1)
else if (chars.head == ')') open > 0 && balanced(chars.tail, open - 1)
else balanced(chars.tail, open)
balanced(chars, 0)
}
Instead of using Switch case you can use recursion to solve your problem in an efficient way.
Following is my code to achieve the same with the help of recursion. You need to convert the string to List for my method.
Code :
object Balance {
def main(args: Array[String]): Unit = {
var paranthesis = "(234(3(2)s)d)" // Use your string here
println(bal(paranthesis.toList)) // converting the string to List
}
def bal(chars: List[Char]): Boolean ={
// var check = 0
def fun(chars: List[Char],numOfOpenParan: Int): Boolean = {
if(chars.isEmpty){
numOfOpenParan == 0
}
else{
val h = chars.head
val n =
if(h == '(') numOfOpenParan + 1
else if (h == ')') numOfOpenParan - 1
else numOfOpenParan
// check = check + n
if (n >= 0) fun(chars.tail,n)
else false
}
}
fun(chars,0)
}
}
My solution for this
def balance(chars: List[Char]): Boolean = {
var braceStack = new Stack[Char]()
def scanItems(strList:List[Char]):Boolean = {
if(strList.isEmpty)
braceStack.isEmpty
else{
var item = strList.head
item match {
case '(' => braceStack.push(item)
scanItems(strList.tail)
case ')'=> if(braceStack.isEmpty){
false
}
else {
braceStack.pop
scanItems(strList.tail)
}
case _ => scanItems(strList.tail)
}
}
}
scanItems(chars)
}
val myStack = new Stack[Char]
def balance(chars: List[Char]): Boolean = {
def processParanthesis(x: Char, a: List[Char]): Stack[Char] = {
if (x == '(') {
myStack.push('(');
} else if (x == ')') {
if (!myStack.empty())
myStack.pop();
else
myStack.push(')');
}
if (a.length == 0)
return myStack;
else
return processParanthesis(a.head, a.tail);
}
return processParanthesis(chars.head, chars.tail).empty();
}
Adding to Vigneshwaran's answer (including comments & filtering unnecessary letters to avoid extra recursive calls):
def balance(chars: List[Char]): Boolean = {
@scala.annotation.tailrec
def recurs_balance(chars: List[Char], openings: Int): Boolean = {
if (chars.isEmpty) openings == 0
else if (chars.head == '(') recurs_balance(chars.tail, openings + 1)
else openings > 0 && recurs_balance(chars.tail, openings - 1)
}
recurs_balance(chars.filter(x => x == '(' || x == ')'), 0)
}
It seems we are attending the same course. my solution:
def balance(chars: List[Char]): Boolean =
doBalance(chars, 0) == 0;
def doBalance(chars: List[Char], parenthesisOpenCount: Int): Int =
if(parenthesisOpenCount <0) -100;
else
if(chars.isEmpty) parenthesisOpenCount
else
chars.head match {
case '(' => return doBalance(chars.tail, parenthesisOpenCount+1)
case ')' => return doBalance(chars.tail, parenthesisOpenCount-1)
case _ => return doBalance(chars.tail, parenthesisOpenCount)
}
