16

我从 scala 开始，并尝试将功能方式应用于它，但我提出了一堆难以阅读的嵌套 if\else 结构，我想知道是否有更好的方法来编写这些东西？

例如，我编写了一个执行括号平衡的脚本：

def balance(chars: List[Char]): Boolean = {
    def checkParentesys(chars: List[Char], parentesis: List[Char]): Boolean =
      if (chars.isEmpty && parentesis.isEmpty)
        true
      else
        if (chars.head == '(')
            checkParentesys(chars.tail, '(' :: parentesis)
        else
            if (parentesis.isEmpty)
                false
            else
                checkParentesys(chars.tail, parentesis.tail)

    checkParentesys(chars.filter(s => s == '(' || s == ')'), List())
  }

我怎样才能把它写得更实用、更像 scala？

4

4 回答 4

27

把它写成折叠可能会更好：

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
于 2012-09-21T05:30:49.030 回答
19

我认为没有任何理由在遍历列表之前对其进行过滤。您可以在遍历列表时忽略非括号。我认为也没有必要建立第二个列表。您真正想知道的是，开括号的计数永远不会是负数：

def balance(chars: List[Char]): Boolean = {
  @tailrec
  def _balance(chars: List[Char], count: Int) : Boolean = 
    chars match {
        case Nil => count == 0   // end of the string did we close every open?
        case '(' :: xs => _balance(xs, count+1)  
        case ')' :: xs => (count > 0) && _balance(xs, count-1) 
        case _ => _balance(chars.tail, count) // uninteresting char, skip it
    }

  _balance(chars, 0)
}
于 2012-09-21T03:59:06.297 回答
4

出色地：

  1. 您可以从编写else if条件开始。
  2. 继续注释它，tailrec因为它是尾递归的。
  3. 过滤条件可以更简单地写成Set('(', ')')，它是一个函数 from ChartoBoolean
  4. 我认为你错过了chars空但parenthesis不是的条件。

所以它看起来像：

def balance(chars: List[Char]): Boolean = {
  @tailrec
  def checkParentesys(chars: List[Char], parentesis: List[Char]): Boolean =
    if (chars.isEmpty && parentesis.isEmpty)
      true
    else if (chars.head == '(')
      checkParentesys(chars.tail, '(' :: parentesis)
    else if (chars.isEmpty || parentesis.isEmpty)
      false
    else
      checkParentesys(chars.tail, parentesis.tail)

  checkParentesys(chars.filter(Set('(', ')')), List())
}

你也可以把整个事情变成一个模式匹配：

def balance(chars: List[Char]): Boolean = {
  @tailrec
  def checkParentesys(chars: List[Char], parentesis: List[Char]): Boolean =
    (chars, parentesis) match {
      case (Nil, Nil) => true
      case ('(' :: charsTail, _) => checkParentesys(charsTail, '(' :: parentesis)
      case (Nil, _) => false
      case (_, Nil) => false
      case (')' :: charsTail, '(' :: parentesisTail) => checkParentesys(charsTail, parentesisTail)
    }
  checkParentesys(chars.filter(Set('(', ')')), List())
}
于 2012-09-21T03:22:03.987 回答
3 
var parens :List[Char] =  Nil
def matcher(chrs: List[Char]): Boolean = {
     if (chrs.isEmpty) {
        return parens.isEmpty
     }
     else {
         chrs.head match {
           case '(' =>  parens = '(' :: parens ;matcher(chrs.tail)
           case ')' =>  if (parens.isEmpty) return false 
                            else if (parens.apply(0) ==  '(') parens = parens.drop(1) 
                            else return false;  
                            matcher(chrs.tail);
           case _ => matcher(chrs.tail)
         }
     }
}

如您所见，我没有使用 count 因为 count 不适用于 ())(

于 2012-09-26T19:42:03.493 回答