如何递归地平衡括号

Question

我正在研究一些代码来平衡括号,这个问题证明对算法最有用.

我用我的第一语言(PHP)实现它,但我正在学习Scala并尝试转换代码.

这是我的PHP代码:

function balanced($string) {
  return isBalanced($string, "");
}

function isBalanced($chars, $stack) {
  if (!strlen($chars))
    return empty($stack);

  switch ($chars[0]) {
    case '(':
      // prepend stack with '(', move to next character
      return isBalanced(substr($chars, 1), $chars[0] . $stack);
    case ')':
      // if '(' seen previously, shift stack, move to next character
      return !empty($stack) && isBalanced(substr($chars, 1), substr($stack, 1));
    default:
      // do nothing to stack, move to next character
      return isBalanced(substr($chars, 1), $stack);
  }
} 

我测试了这个,它有效.但是,当我将其转换为Scala时,它在平衡字符串上失败.

我的Scala代码:

object Main {
  def balance(chars: List[Char]): Boolean = {
    def balanced(chars: List[Char], stack: String): Boolean = {
      if (chars.isEmpty)
        stack.isEmpty
      else if (chars.head == ')')
        balanced(chars.tail, chars.head + stack)
      else if (chars.head == '(')
        !stack.isEmpty && balanced(chars.tail, stack.tail)
      else
        balanced(chars.tail, stack)
    }

    balanced(chars, "")
  }
}

我很欣赏这不是最好的Scala代码,但我刚刚开始.一些测试:

balance("(if (0) false (x))".toList) - fails
balance("profit and loss (P&L).\n(cashflow)".toList) - fails
balance(":)".toList) - passes
balance(")(()".toList) - passes

PHP等价物通过了所有这些测试.我在Scala实现中做错了什么？

Answer 1

对于它的价值,这是一个更惯用的Scala实现:

def balance(chars: List[Char]): Boolean = {
  @tailrec def balanced(chars: List[Char], open: Int): Boolean = 
    chars match {
      case      Nil => open == 0
      case '(' :: t => balanced(t, open + 1)
      case ')' :: t => open > 0 && balanced(t, open - 1)
      case   _ :: t => balanced(t, open)
    }

  balanced(chars, 0)
}

Answer 2

为了完整起见,我从另一个SO问题中找到了更简洁的"scala-esque"实现:

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

Answer 3

你把案件混淆了(和).

Answer 4

与Aaron Novstrup的答案相同,但使用'if else'.我也参加了同样的课程,但是到目前为止,我们只是被教导.

def balance(chars: List[Char]): Boolean = {
    def balanced(chars: List[Char], open: Int): Boolean = 
      if (chars.isEmpty) open == 0
      else if (chars.head == '(') balanced(chars.tail, open + 1)
      else if (chars.head == ')') open > 0 && balanced(chars.tail, open - 1)
      else balanced(chars.tail, open)
    balanced(chars, 0)
}