有人可以向我解释括号平衡问题的算法吗?
"由于匹配的括号对,字符串(代码)语法是否正确?"
除了对于每个"("应该有另一个")"以使算法返回true这一事实之外,我无法弄清楚。
谢谢!
我找到了这个解决方案,但我不明白它,我不想复制和粘贴它:
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)
}
此代码通过在没有第一个元素的字符串上调用balanced()来递归检查字符串是否包含匹配数量的左括号和右括号。
字符串中括号的预期值保持在一种平衡指示器打开中 - 正数表示所需的")"量,负数表示所需"("的数量。初始余额为 0。
当递归到达字符串末尾时,它会检查平衡是否正常(打开 == 0),例如,看到匹配数量的括号。
还有一个检查(打开> 0),以确保在有"("之前没有遇到")",它可以关闭。