4

私は括弧のバランスをとるためにいくつかのコードに取り組んでいます、この質問はアルゴリズムにとって最も有用であることがわかりました。

私はそれを私の第一言語（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の実装で何を間違えましたか？

4

9 に答える 9

24

価値のあるものとして、より慣用的な 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)
}
于 2012-09-23T21:59:20.537 に答える
9

Aaron Novstrupの回答と同じですが、「ifelse」を使用します。私も同じコースに参加していますが、これまでのところ、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)
}
于 2012-10-23T11:18:24.370 に答える
9

完全を期すために、別の SO questionからさらに簡潔な「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
于 2012-09-24T13:16:38.517 に答える
8

(とのケースを混同しました)。

于 2012-09-23T18:47:15.970 に答える
-2

同じコースを受講しているようです。私の解決策：

def balance(chars: List[Char]): Boolean = 
doBalance(chars, 0) == 0;
def doBalance(chars: List[Char], parenthesisOpenCount: Int): Int =
if(parenthesisOpenCount <0) -100;
else
if(chars.isEmpty) parenthesisOpenCount
else
  chars.head match {
  case '(' => return doBalance(chars.tail, parenthesisOpenCount+1) 
  case ')' => return doBalance(chars.tail, parenthesisOpenCount-1)
  case _ => return doBalance(chars.tail, parenthesisOpenCount)
}
于 2012-09-25T17:50:58.930 に答える