圆括号平衡算法
圆括号平衡算法
提问于 2016-09-30 09:45:27
我正在使用scala中的一个小程序来检查关于括号的开始和结束是否正确地形成了某些表达式i。这是作为here的问题，但我自己的程序。
def balance(chars: List[Char]): Boolean = {
def balanced(chars: List[Char], opened: Int, closed: Int): Boolean = {
if (chars.isEmpty && opened == closed) true
else if (opened < closed) false
else {
if (chars.head == '(') balanced(chars.tail, opened + 1, closed)
if (chars.head == ')') balanced(chars.tail, opened, closed + 1)
else balanced(chars.tail, opened, closed)
}
}
balanced(chars, 0, 0)}
println(balance(只是(一些随机的)句子).\n(不起作用)“.toList)
问题是，例如，它对此示例不起作用。我跟踪了这个程序，很明显，当我们从递归调用返回时，问题就出现了，但是我不知道错误是什么。
回答 2
Stack Overflow用户
回答已采纳
发布于 2016-09-30 10:03:44
在……里面
else {
if (chars.head == '(') balanced(chars.tail, opened + 1, closed)
if (chars.head == ')') balanced(chars.tail, opened, closed + 1)
else balanced(chars.tail, opened, closed)
}如果要将两个独立的if表达式视为单个案例表达式，则它们是独立的。如果chars.head == '('是true，则进行递归调用，但忽略结果并计算第二个if。这将导致采取else分支，这实际上忽略了在第一个表达式中找到的(。你可以使用match。
chars match {
case Nil => opened == closed
case '('::cs => balanced(cs, opened + 1, closed)
case ')'::cs => balanced(cs, opened, closed + 1)
case _::cs => balanced(cs, opened, closed)
}Stack Overflow用户
发布于 2016-09-30 09:58:28
在上面的例子中，如果您有"sss)fff(“它也给出了真，所以它会在逻辑上出错)，您也可以尝试下面的代码。
def balance(chars: List[Char]): Boolean = {
def balrec(chars: List[Char], accr: Int, accl: Int): Boolean = {
chars match {
case head :: tail =>
if (head.equals('(')) balrec(tail, accr + 1, accl)
else if (head.equals(')') && (accr > accl || accr == 0)) balrec(tail, accr, accl + 1)
else balrec(tail, accr, accl)
case Nil => if (accr == accl) true else false
}
}
balrec(chars, 0, 0)
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/39788482
复制相关文章
相似问题
腾讯云开发者
