Минимальная валидность скобок

Дана строка s, состоящая из скобок ( и ). Необходимо посчитать, какое минимальное количество скобок необходимо добавить к строке s, чтобы каждая скобка имела закрывающую/открывающую ее пару.

Пример 1:

**Дано:** "())"
**Результат:** 1

Пример 2:

**Дано:** "()()()"
**Результат:** 0

Пример 3:

**Дано:** "()()))"
**Результат:** 2

Пример 4:

**Дано:** "((()()))"
**Результат:** 0