UniLecs #158. Баланс скобок - 2

Задача: дана строка, содержащая скобки вида ( и ). Скобочное выражение считается правильным, если: для каждой открывающей скобки справа от нее есть соот-щая закрывающая скобка и наоборот. 

Необходимо определить наименьшее количество скобок, которые нужно вставить в исходную строку для того, чтобы исходная строка стала правильной.

Входные данные: str - строка, содержащая только скобки вида ( или ). Размер строки от 1 до 1000 символов.

Вывод: наименьшее кол-во скобок.

Пример:

1. str = "((()))"; Answer = 0.

2. str = "((()"; Answer = 2.

Идея: мы уже решали похожую задачу, где нужно было просто определить, является ли заданное скобочное выражение правильным. Тогда для решения задачи мы использовали стек.

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

Итак, получаем: balance = 0; tempCounter = 0;

1. Если встречаем открывающуюся скобку '(', то увеличиваем счетчик balance. Если встречаем закрывающуюся скобку ')', то уменьшаем счетчик balance.
2. Если на очередной итерации счетчик balance стал меньше нуля, то увеличиваем счетчик tempCounter и обнуляем счетчик balance, т.е. мы увеличиваем счетчик пропущенных скобок и обнуляем баланс.
3. После обхода строки сумма счетчика balance и tempCounter даст нам искомый результат. Это и будет наименьшим кол-вом скобок, которые необходимо добавить в исходную строку, чтобы она стала правильным скобочным выражением.

Реализация:

https://gist.github.com/unilecs/f034cca4b12f9f52e8c996b1250bda39

Play-test: https://dotnetfiddle.net/6ybwMj