如何使用scala，递归，一个函数和一个函数参数进行括号平衡

Question

我正在构建一个使用 scala 和递归来平衡括号的小方法。

我出了这段代码，令人惊讶的是它不起作用。

object Test{
def balance(chars: List[Char]): Boolean=
{
  var opening_index: Int = -1
  var  closing_index: Int = -1
  opening_index = chars.indexOf('(')
  closing_index = chars.indexOf(')')
  println(opening_index)
  println(closing_index)
  if ( chars.size == 0 ) true

  if ((opening_index == -1) & (closing_index== -1))
    {
      true
    }
  if (closing_index> -1 & opening_index> -1)
    {
      if (closing_index< opening_index) return(false)
      else
      {
        balance(chars.filter(_!=chars(closing_index)).filter(_!=chars(opening_index)))
      }
    }
  else
    return (false)
}

  val lst:List[Char] = List('(',')' ,'3','4')
  balance(lst)
}

我知道还有其他类似的帖子，但我对使用这种方法比其他方法更感兴趣。

Answer 1

您可能

希望按索引而不是按字符进行筛选。实际上，您的代码会擦除第一轮中的所有括号。

这适用于zipWithIndex，并将索引与opening_index和closing_index进行比较：

def balance(chars: List[Char]): Boolean = {
  val opening_index = chars.indexOf('(')
  val closing_index = chars.indexOf(')')
  if ( chars.size == 0 ) {
    true 
  } else if ((opening_index == -1) && (closing_index== -1)) {
    true
  } else if (closing_index > -1 && opening_index > -1) {
    if (closing_index < opening_index) {
      false
    } else {
      balance(
        chars.zipWithIndex.filterNot{ 
          case (c, i) => i == opening_index || i == closing_index
        }.map(_._1)
      )
    }
  } else {
    false
  }
}
println(balance("()34".toList))
println(balance("()34)".toList))
println(balance("(x)(y(z))".toList))
println(balance("(x)(y(z)".toList))

输出：

true
false
true
false

Answer 2

您可以使用以下解决方案来检查余额括号。

object Driver extends App{
  def balance(chars: List[Char]): Boolean=
  {
    if (chars.mkString("").length() == 0) {
      return true;
    }
    if (chars.mkString("").contains("()")) {
      return balance(chars.mkString("").replaceFirst("\(\)", "").toCharArray.toList);
    }
    if (chars.mkString("").contains("[]")) {
      return balance(chars.mkString("").replaceFirst("\[\]", "").toCharArray.toList);
    }
    if (chars.mkString("").contains("{}")) {
      return balance(chars.mkString("").replaceFirst("\{\}", "").toCharArray.toList);
    } else {
      return false;
    }
  }

  println(balance(List('(','{','}')))
  println(balance(List('(','{','}',')')))
}

Answer 3

此代码有两个主要(功能(问题。

首先，这个测试什么都不做，因为结果被扔掉了

if ((opening_index == -1) & (closing_index== -1))
{
  true
}

你可能的意思是return true

其次，递归调用是错误的

balance(chars.filter(_ != chars(closing_index)).filter(_ != chars(opening_index)))

对filter的这两个调用将从列表中删除所有括号，因此即使列表的其余部分不平衡，对balance的调用也将始终成功。您可能希望使用三个slice调用来删除 opening_index 和 closing_index 处的特定括号。