如何递归地平衡括号 [英] How to balance parenthesis recursively

问题描述

我正在编写一些代码来平衡括号，这个问题证明了大多数对算法有用.

I'm working on some code to balance parenthesis, this question proved most useful for the algorithm.

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

I implemented it in my first language (PHP) but I'm learning Scala and trying to convert the code.

这是我的 PHP 代码:

Here is my PHP code:

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 时，它在平衡字符串上失败.

I've test this, it works. However, when I convert it to Scala, it fails on balanced strings.

我的 Scala 代码:

My Scala code:

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 代码，但我才刚刚开始.一些测试:

I appreciate this isn't the best Scala code but I'm just starting out. Some tests:

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 实现中做错了什么?

The PHP equivalent passes all these tests. What have I done wrong in my Scala implementation?

推荐答案

您混淆了 ( 和 ) 的情况.

You have mixed up the cases for ( and ).

这篇关于如何递归地平衡括号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！