括号平衡算法递归 [英] Parenthesis Balancing Algorithm recursion

问题描述

有人可以向我解释括号平衡问题的算法吗?

由于括号匹配，字符串(代码)语法是否正确?"

除了对于每个("应该有另一个)"的算法返回true之外，我无法弄清楚.

谢谢！

我找到了这个解决方案，但我不明白，我不想复制和粘贴它:

def balance(chars: List[Char]): Boolean = {def平衡(字符:列表[字符]，打开:Int):布尔={if (chars.isEmpty) 打开 == 0别的if (chars.head == '(') 平衡(chars.tail,open+1)别的if (chars.head == ')') open>0 &&平衡(chars.tail，open-1)否则平衡(chars.tail，打开)}平衡(字符，0)}

解决方案

此代码通过在没有第一个元素的字符串上调用 balanced() 递归地检查字符串是否包含匹配数量的左括号和右括号.

字符串中括号的期望值保持在一种平衡指示器中开放 - 正数表示所需的数量 ')' 和所需的负数 '('.初始余额为 0.>

当递归到达字符串末尾时，它会检查余额是否正常(open == 0)，例如看到了匹配数量的括号.

还有一个检查 (open > 0) 以确保在出现 '(' 它可以关闭.

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.

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)
 }

解决方案

This code recursively checks if string contains matching amount of opening and closing parentheses by calling balanced() on the string without first element.

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.

When recursion reaches end of string it checks if balance is ok (open == 0), e.g. there was matching amount of parentheses seen.

There is also a check (open > 0) to ensure that ')' wasn't encountered before there was '(' it could close.

这篇关于括号平衡算法递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！