Сколько скобок не хватает

Скобочная строка валидна, когда каждой открывающей ( нашлась закрывающая ) в правильном порядке. Дана строка s, состоящая только из скобок. Верни минимальное количество скобок, которое нужно добавить, чтобы строка стала валидной.

Примеры

Ввод
"())"
Вывод
1
Ввод
"((("
Вывод
3
Ввод
"()"
Вывод
0

Нужно реализовать

def min_add_to_make_valid(s: str) -> int:

Теги

stringsstack
PostgreSQLv16

Здесь будет результат выполнения кода

Видимые тесты
1
Ввод
"())"
Ожидаемый1
2
Ввод
"((("
Ожидаемый3
3
Ввод
"()"
Ожидаемый0
4
Ввод
"()))(("
Ожидаемый4
5
Ввод
""
Ожидаемый0
6
Ввод
")("
Ожидаемый2
Фокус-радио
На паузе · SomaFM · Fluid