scala 括号平衡算法递归
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19818569/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Parenthesis Balancing Algorithm recursion
提问by user2947615
Can somebody explain to me the algorithm for the Parenthesis Balancing problem?
有人可以向我解释括号平衡问题的算法吗？
"Is the string (code) syntax correct on account of matching parentheses couples?"
“由于匹配的括号对，字符串（代码）语法是否正确？”
I can't figure it out apart from the fact that for each " ( " there should be another " ) " for the algorithm to return true.
除了对于每个“（”应该有另一个“）”算法返回true这一事实之外，我无法弄清楚。
Thanks!
谢谢！
I found this solution but I do not understand it and I don't want to copy and paste it:
我找到了这个解决方案，但我不明白，我不想复制和粘贴它：
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)
}
采纳答案by arkonautom
This code recursively checks if string contains matching amount of opening and closing parentheses by calling balanced()on the string without first element.
此代码通过在没有第一个元素的字符串上调用balance()递归地检查字符串是否包含匹配数量的左括号和右括号。
Expectancy of parentheses in the string is kept in a kind of balance indicator open- positives indicate amount of needed ')' and negatives amount of needed '('. Initial balance is 0.
在字符串中括号预期被保持在一种平衡指示器的开-阳性指示的所需量“）”和所需“（”初始余额为0底片量。
When recursion reaches end of string it checks if balance is ok (open == 0), e.g. there was matching amount of parentheses seen.
当递归到达字符串末尾时，它会检查余额是否正常（open == 0），例如看到匹配数量的括号。
There is also a check (open > 0) to ensure that ')' wasn't encountered before there was '(' it could close.
还有一个检查 (open > 0) 以确保在出现 '(' 它可以关闭之前没有遇到 ')'。
