Algorithm to check matching parenthesis

Question

This relates to the Coursera Scala course so I want to directly ask you NOT to give me the answer to the problem, but rather to help me debug why something is happening, as a direct answer would violate the Coursera honor code.

I have the following code:

    def balance(chars: List[Char]): Boolean = {
    val x = 0
    def loop(list: List[Char]): Boolean = {
      println(list)

      if (list.isEmpty) if(x == 0) true
      else if (list.head == '(') pushToStack(list.tail)
      else if (list.head == ')') if(x <= 0) false else decreaseStack(list.tail)
      else loop(list.tail)


      true
    }

    def pushToStack(myList: List[Char]) { x + 1; loop(myList)}

    def decreaseStack(myList: List[Char]) { x - 1; loop(myList)}

    loop(chars)
  }

A simple explanation:

If the code sees a "(" then it adds 1 to a variable. If it sees a ")" then it first checks whether the variable is equal to or smaller than 0. If this is the case, it returns false. If the value is bigger than 0 then it simply decreases one from the variable.

I have tried running the following:

if(balance("This is surely bad :-( ) (".toList)) println("balanced") else println("not balanced");

Clearly this is not balanced, but my code is returning balanced.

Again: I am not asking for help in writing this program, but rather help in explained why the code is returning "balanced" when clearly the string is not balanced

--EDIT--

  def balance(chars: List[Char]): Boolean = {

    val temp = 0;

   def loop(list: List[Char], number: Int): Boolean = {
      println(list)

      if (list.isEmpty) if(number == 0) true
      else if (list.head == '(') loop(list.tail, number + 1)
      else if (list.head == ')') if(number <= 0) false else loop(list.tail, number - 1)
      else loop(list.tail,number)


      true
    }


    loop(chars,0)
  }

^^ Still prints out balanced

Answer 1

You are using an immutable x when you really want a mutable x.

Here, let me rewrite it for you in a tail recursive style to show you what you're actually doing:

@tailrec def loop(myList: List[Char], cur: Int = 0): Boolean = myList match{
  case "(" :: xs => 
    val tempINeverUse = cur+1
    loop(xs, cur) //I passed in 0 without ever changing "cur"!
  case ")" :: xs if cur < 0 => false //This is a bug, regardless if you fix the rest of it
  case ")" :: xs => 
    val tempINeverUse = cur-1
    loop(xs, cur) //Passed in 0 again!
  case x :: xs => loop(xs, cur)
  case Nil => cur == 0 //Since I've never changed it, it will be 0.
}

Answer 2

You need to keep a context of parenthesis in comments or in quotes as well. You can use a counter to achieve that. If the counter is set for a comment or a double quote then ignore any parenthesis that comes your way. Reset the counter whenever you find a finishing comment or double quote