Рекурсия алгоритма балансировки Parenthesis

Может ли кто-нибудь объяснить мне алгоритм проблемы балансировки скобок?

"Правильно ли синтаксис строки (кода) из-за сопоставления пар круглых скобок?"

Я не могу понять это, кроме того, что для каждого "(" должен быть другой ")", чтобы алгоритм возвращал 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)
 }

Ответы

Ответ 1

Этот код рекурсивно проверяет, содержит ли строка соответствующее количество открывающих и закрывающих круглых скобок, вызывая balanced() в строке без первого элемента.

Ожидание круглых скобок в строке сохраняется в виде индикатора баланса open - положительные значения указывают количество необходимых ")" и отрицательные суммы необходимых "(" Начальный баланс равен 0.

Когда рекурсия достигает конца строки, она проверяет, нормально ли баланс (open == 0), например. было сопоставимое количество скобок.

Существует также проверка (open > 0), чтобы убедиться, что ')' не встречался до того, как был "(" он может закрыть ".