balanced brackets algorithm using mutable stack in scala

Question

I have recently interview for scala. The question is to solve whether the given string is having balanced brackets or not.

For example, "(({[]}))" is balanced where "((({)}))" is not.

I have provided below solution -

    object BalancedBrackets {

      def main(a: Array[String]): Unit = {
        println(balancedBrackets("((()))"))
      }


      def balancedBrackets(s: String): Boolean = {

        import scala.collection.mutable.Stack
        import scala.util.control.Breaks._
        var brackets = Stack[Char]()
        try {
          for (c <- s) {
            println(c)
            c match {
              case '(' | '{' | '[' => brackets.push(c)
              case ')' => var c1 = brackets.pop; if (c1 != '(') {
                break
              }
              case '}' => var c1 = brackets.pop; if (c1 != '{') {
                break
              }
              case ']' => var c1 = brackets.pop; if (c1 != '[') {
                break
              }
            }
          }

          if (brackets.size == 0) true else false
        } catch {
          case ex: Exception => println("Exception"); ex.printStackTrace(); false
        }
      }

    }

But the interviewer asked to to use the immutable stack instead of mutable as mutable is not thread-safe and it won't work as expected in multi threaded environment.

I am not sure how to implement the same algorithm in scala using immutable stack. Can anyone help me with the same.

Here is the solution: http://stackoverflow.com/a/12556621/4496364 — insan-e, Jul 24 '16 at 23:11
Possible duplicate of [Algorithm converted to Scala, can't see why it doesn't work](http://stackoverflow.com/questions/12555162/algorithm-converted-to-scala-cant-see-why-it-doesnt-work) — insan-e, Jul 24 '16 at 23:12
Read the book: [Functional Programming in Scala](https://www.manning.com/books/functional-programming-in-scala). You should write tail recursive algorithm with accumulator, or foldLeft. — Andrzej Jozwik, Jul 25 '16 at 13:45

score 2 · Accepted Answer · answered Jul 25 '16 at 13:26

As in your solution stack contains only brackets. If next bracket in text matches top bracket in stack they are eliminated otherwise stack grows. Brackets are considered balanced when resulting stack is empty.

The main advantage of foldLeft is that it abstracts over for loop. What is left from loop is a function from previous result and current value to next result (Stack[Char], Char) => Stack[Char]. Such signature encourages to return new stack for each iteration.

def balanced(text: String): Boolean = {
  val parenthesis = Map('}' -> '{', ')' -> '(', ']' -> '[', '>' -> '<')

  val isParenthesis: (Char) => Boolean = c => parenthesis exists { case (closed, opened) => closed == c || opened == c }
  val isClosing: (Char) => Boolean = parenthesis.contains
  val openingFor: (Char) => Option[Char] = parenthesis.get

  text.toCharArray
    .filter(isParenthesis)
    .foldLeft(Stack[Char]())((stack, p) => {
      if (isClosing(p) && openingFor(p) == stack.headOption) stack.pop
      else stack.push(p)
    }).isEmpty
}

Michel Henrique · Answer 2 · 2016-07-25T00:24:31.590

I readed your problem and I`ve come up with this solution :

def balancedBrackets(s: String): Boolean =
            s.substring(0,s.length/2)  == s.substring(Math.floorDiv(s.length(),2)).map {
            x => if(x == ')') '('
                 else if(x == ']') '['
                 else if(x == '}') '{'
              }.mkString.reverse

As you can see there is no state mutation.

If you want to work with Scala, you have to search a little bit more on functional programming.

I recommend that you read "Functional Programming in Scala" and "Programming in Scala" both are great books ! I would start by "Functional Programming in Scala" since it will introduce to you this new paradigm of programming.

score 1 · Answer 3 · answered Apr 21 '18 at 12:04

Here is another solution with using recursive function, which is unlike foldLeft supports early interruption and hence more effective. Some test cases are included. Also I'm using linked list instead of stack, it's immutable and has the same efficiency as immutable stack.

import org.scalatest.{FunSuite, Matchers}

import org.scalatest.prop.TableDrivenPropertyChecks._
import org.scalatest.prop.Tables.Table

class ExpressionValidatorTest extends FunSuite with Matchers {

  object ExpressionValidator {
    import scala.annotation.tailrec

    private val matchingBrackets = Map('(' -> ')', '{' -> '}', '[' -> ']')
    private val openBrackets = matchingBrackets.keySet

    def validate(input: String): Boolean = {

      @tailrec
      def isValid(input: List[Char], stack: List[Char] = Nil): Boolean = (input, stack) match {
        case (nextBracket +: tail, _) if openBrackets.contains(nextBracket) => isValid(tail, nextBracket +: stack)
        case (nextBracket +: tail, lastBracket +: stackTail) if matchingBrackets(lastBracket) == nextBracket => isValid(tail, stackTail)
        case (Nil, _) => stack.isEmpty
        case _ => false
      }

      input.length % 2 == 0 && isValid(input.toCharArray.toList)
    }
  }

  test("validate") {
    val inputs = Table(
      ("expression", "expectedResult"),
      ("()", true),
      ("({})", true),
      ("({[]})", true),
      ("({[()]})", true),
      ("({[()]}())", true),
      ("()()()", true),
      ("(", false),
      (")", false),
      ("({)}", false),
      ("({)", false),
      ("(]", false),
      ("({[(])})", false)
    )

    forAll(inputs) { case (input, expected) => ExpressionValidator.validate(input) shouldBe expected }
  }

}

balanced brackets algorithm using mutable stack in scala

3 Answers3