3

我写了一个递归括号平衡函数，代码中似乎没有任何错误，但是当我运行它时，我得到了很多错误。

我用这样的调用编写了函数：

if(balance("blarg(arg)".toList)) println("true!") else println("false")

和这样的定义：

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

      implicit class MutableInt(var value: Int) 
      {
          def inc() = { value+=1 } 
          def dec() = { value-=1 }                  
      }

        var stack: Int = 0

        def recursbalance(chars: List[Char], stack: Int): Boolean=
        {

            if ((chars.head: Char) == "(".toList) stack.inc()
            else if ((chars.head: Char) == ")".toList) stack.dec()

            if (stack<0) false

            if (chars.isEmpty: Boolean) if (stack == 0) true else false  

            recursbalance(chars.tail: List[Char], stack: Int)

        }
    recursbalance(chars: List[Char], stack: Int)
}

我收到这些错误：

Exception in thread "main" java.util.NoSuchElementException: head of empty list
at scala.collection.immutable.Nil$.head(List.scala:337)
at scala.collection.immutable.Nil$.head(List.scala:334)
at recfun.Main$.recursbalance$1(Main.scala:45)
at recfun.Main$.balance(Main.scala:55)
at recfun.Main$.main(Main.scala:16)
at recfun.Main.main(Main.scala)

我该如何解决？抱歉，我是 Scala 新手。

我尝试用这个替换我的递归调用：

   if (chars.isEmpty: Boolean) {
       if (stack == 0) true else false  
   }
   else
       recursbalance(chars.tail: List[Char], stack: Int)

但我仍然得到了所有的错误..

4

2 回答 2

3

您需要List在调用之前检查您是否为空head，match这可能是最好的方法：

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

    def recursbalance(chars: List[Char], stack: Int): Int = chars match {
      case Nil => stack
      case ')' :: tail => recursbalance(tail, stack - 1)
      case '(' :: tail => recursbalance(tail, stack + 1)
      case x :: tail => recursbalance(tail, stack)
    }
    recursbalance(chars, 0) == 0;
  }

我已经稍微更改了您的方法以删除MutableInt并Int直接在内部使用。

我进行了快速检查：

  println(balance("())".toList));
  println(balance("(())".toList));

输出

false
true
于 2013-03-29T16:43:05.100 回答
0

代码中的特定错误是运行时错误。Scala 编译器无法发现它会在编译时失败。这就是代码在 IDE 中看起来不错的原因。但是，当您运行它时，会出现错误。它源于以下几行：

def recursbalance(chars: List[Char], stack: Int): Boolean=
{
  if ((chars.head: Char) == "(".toList) stack.inc()

  // ... 

  recursbalance(chars.tail: List[Char], stack: Int)
}

您使用比前一个元素短一个元素的列表重复调用 recursbalance。所以在某些时候列表是空的，你尝试从空列表中获取头元素。那是你得到 java.util.NoSuchElementException 的时候。

在您的代码中还有一些其他的事情需要指出。例如，您在 if 条件中将 Char 与 List[Char] （字符列表）进行比较。这将始终评估为假。

于 2013-03-29T16:51:45.660 回答