Валидация корректности расположения круглых скобок в строке

Условие

Реализуйте функцию, принимающую строку и определяющую, правильно ли в ней расставлены круглые скобки ( и ). Функция должна возвращать true, если каждая открывающая скобка имеет соответствующую закрывающую и порядок вложения соблюдён, и false в противном случае.

function validateParentheses(str: string): boolean {
    // implementation
}

// validateParentheses('(') === false
// validateParentheses(')') === false
// validateParentheses('()') === true
// validateParentheses('(())') === true
// validateParentheses(')(') === false
// validateParentheses(')()(') === false

Ответ

Для круглых скобок достаточно счётчика: увеличиваем его на открывающей и уменьшаем на закрывающей. Отрицательное промежуточное значение или ненулевой итог означают ошибку.

function validateParentheses(str: string): boolean {
  let balance = 0;
  for (const ch of str) {
    if (ch === '(') balance++;
    else if (ch === ')' && --balance < 0) return false;
  }
  return balance === 0;
}

Другие символы здесь игнорируются. Пустая строка корректна. Проверка отрицательного баланса обязательна: у строки ')(' итоговый баланс нулевой, но порядок неправильный. Время O(n), память O(1).