检查匹配括号的算法

Question

这与 Coursera Scala 类(class)有关，所以我想直接要求您不要给我问题的答案，而是帮助我调试为什么会发生某些事情，因为直接回答会违反 Coursera 荣誉守则。

我有以下代码:

    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)
  }

一个简单的解释:

如果代码看到一个“(”，那么它会把一个变量加 1。如果它看到一个“)”，那么它首先检查变量是否等于或小于 0。如果是这样，它返回 false .如果该值大于 0，则它只是从变量中减一。

我试过运行以下命令:

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

显然这不是平衡的，但我的代码正在返回平衡。

再说一次:我不是在编写这个程序时寻求帮助，而是帮助解释为什么当字符串明显不平衡时代码返回“平衡”

--编辑--

  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)
  }

^^ 仍然打印出平衡的

Answer 1

当你真的想要一个可变的 x 时，你正在使用一个不可变的 x。

在这里，让我以尾递归的方式为您重写它，以向您展示您实际在做什么:

@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.
}