Parenthesis Balancing Algorithm recursion
谁能给我解释一下括号平衡问题的算法？
“由于匹配括号对，字符串(代码)语法是否正确？”
除了每个”(“应该有另一个”)”让算法返回 true 之外，我无法弄清楚。
谢谢！
我找到了这个解决方案，但我不明白，我不想复制和粘贴它：
|
1
2 3 4 5 6 7 8 9 10 11 |
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。
当递归到达字符串末尾时，它会检查余额是否正常(open == 0)，例如看到匹配数量的括号。
还有一个检查 (open > 0) 以确保在有 ‘(‘ 它可以关闭之前没有遇到 ‘)’。
- 最后一件事……在这一行中： if (chars.head == \\’)\\’) open>0
来源：https://www.codenong.com/19818569/
