Сколько скобок нужно перевернуть, что бы сбалансировать строку из строк

Поскольку это учебное задание могу только подсказать возможный ход мысли.

Можете идти по скобкам и считать баланс тех и других скобок. И смотрите, в каком случае их нужно переворачивать, а в каком нет. Например, открывающая скобка увеличивает баланс на 1, а закрывающая уменьшает на 1. Что будет, если баланс в какие-то моменты будет отрицательным? А если положительным? А что будет, если после прохода по всем скобкам баланс будет положительный? А если отрицательный? Вот надо ответить на все эти вопросы и понять, что со всем этим делать.

У меня получилось такое решение.
Считаю открывающиеся скобки как +1 и закрывающиеся как -1.
Постулата два:

1. Если при подсчёте баланса скобок получили -1, то скобку однозначно нужно переворачивать, ибо закрывающихся скобок на данный момент получается больше чем открывающихся.
2. Если до конца строки осталось столько символов сколько текущий баланс скобок, то оставшиеся скобки однозначно надо чтобы были закрывающимися.

def balance(s):
    n = count = 0
    result = ""
    s = list(s)
    while s:
        ch = s.pop(0)
        n += -1 if ch == ")" else +1
        if n < 0:  # закрывающаяся скобка раньше открывающейся - надо менять
            ch = "{"
            count += 1
            n += 2
        elif n > len(s): # открытых скобок набралось столько, что оставшиеся до конца надо все закрывать
            if ch == "(":
                ch = "}"
                count += 1
                n -= 2
        result += ch
    return (count, result)

tests = ["(((())", ")()(", "(()(())()())))", "))))", 
         "((((((", "(((()(", ")()()(((((", "())())",
         "(()())", "(()((()()())))"]
for test in tests:
    print(test, "==>", *balance(test))

Ну или если выкинуть все "рюшечки" из кода:

def balance(s):
    n = count = 0
    for i,ch in enumerate(s):
        if (not n and ch == ")") or (n >= len(s)-i and ch == "("):
            ch = "(" if ch == ")" else ")"
            count += 1
        n += -1 if ch == ")" else +1
    return count

Для наглядности ещё собирается конечная строка со скобками, где фигурными скобками обозначаются те скобки, что были перевёрнуты.
Результат:

(((()) ==> 1 (((}))
)()( ==> 2 {()}
(()(())()()))) ==> 1 (()(())()()){)
)))) ==> 2 {){)
(((((( ==> 3 (((}}}
(((()( ==> 2 (((})}
)()()((((( ==> 4 {()()((}}}
())()) ==> 1 (){())
(()()) ==> 0 (()())
(()((()()()))) ==> 0 (()((()()())))