Шаг 1

Эту задачу частенько можно встретить на собеседованиях. Возможно, с такой проблемой вы уже сталкивались и так или иначе успешно решали. Звучит она довольно просто: в данном нам тексте нужно провалидировать, что все скобки корректно расставлены. Например, (((())())) является корректной расстановкой, а ()( — нет. Если вы ещё не решали эту задачу, остановитесь и попробуйте сами.

import {test} from "./tester"

/*
Примеры:
validateparenthesis('(((())()))') => true
validateparenthesis('())') => false
*/

function validateparenthesis(text) {
  return true;
}

test(validateparenthesis('(((())()))'), true);
test(validateparenthesis('())'), false);

Шаг 2

Решение, которое первым приходит в голову — просто посчитать количество открывающих и закрывающих скобок и сравнить эти числа. Наши тесты на этом решении проходят.

import {test} from "./tester"

/*
Примеры:
validateparenthesis('(((())()))') => true
validateparenthesis('())') => false
*/

function validateparenthesis(text) {
  const openingparenthesisCount = text.split('').filter(character => character === '(').length;
  const closingparenthesisCount = text.split('').filter(character => character === ')').length;

  return openingparenthesisCount === closingparenthesisCount;
}

test(validateparenthesis('(((())()))'), true);
test(validateparenthesis('())'), false);

Шаг 3

Однако если мы введем ещё один пример, то наше решение не сработает и сломается — например, об )(. Это, кстати, ещё одно важное правило. Если вы думаете, что пришли к решению, попробуйте придумать ещё несколько примеров входных данных: возможно, вы рассмотрели не все случаи.

import {test} from "./tester"

/*
Примеры:
validateparenthesis('(((())()))') => true
validateparenthesis('())') => false
validateparenthesis(')(') => false
*/

function validateparenthesis(text) {
  const openingparenthesisCount = text.split('').filter(character => character === '(').length;
  const closingparenthesisCount = text.split('').filter(character => character === ')').length;

  return openingparenthesisCount === closingparenthesisCount;
}

test(validateparenthesis('(((())()))'), true);
test(validateparenthesis('())'), false);
test(validateparenthesis(')('), false);

Шаг 4

Давайте подумаем, как можно решить эту задачу. По мере продвижения по тексту у нас могут встречаться скобки. Если мы встречаем открывающую скобку, то увеличиваем уровень вложенности на один, а если закрывающую — уменьшаем. Например: (вот здесь мы имеем первый уровень вложенности скобок (тут второй), здесь снова первый), а тут уже вложенности нет совсем.

import {test} from "./tester"

/*
Примеры:
validateparenthesis('(((())()))') => true
validateparenthesis('())') => false
validateparenthesis(')(') => false
*/

function validateparenthesis(text) {
  return true;
}

test(validateparenthesis('(((())()))'), true);
test(validateparenthesis('())'), false);
test(validateparenthesis(')('), false);

Шаг 5

Тогда можно сделать довольно простой алгоритм, который будет увеличивать и уменьшать уровень вложенности в зависимости от того, какую скобку мы встречаем. Если в конце мы будем иметь нулевую вложенность и по ходу алгоритма не уйдём в минус — то будем считать, что скобки расставлены верно.

  import {test} from "./tester"

/*
Примеры:
validateparenthesis('(((())()))') => true
validateparenthesis('())') => false
validateparenthesis(')(') => false
*/

function validateparenthesis(text) {
  let parenthesisCount = 0;

  for (const character of text) {
    if (character === '(') {
      parenthesisCount++;
    }

    if (character === ')') {
      if (parenthesisCount === 0) {
        return false;
      }

      parenthesisCount--;
    }
  }

  return parenthesisCount === 0;
}

test(validateparenthesis('(((())()))'), true);
test(validateparenthesis('())'), false);
test(validateparenthesis(')('), false);

Шаг 6

А ещё эту задачу можно решить при помощи стека: каждая скобка, увеличивающая вложенность, будет отправляться наверх стека, а каждая закрывающая — доставать её оттуда. Выглядеть это будет примерно так же, как и в решении со счётчиком, но вместо счётчика появится вспомогательный массив.

 import {test} from "./tester"

/*
Примеры:
validateparenthesis('(((())()))') => true
validateparenthesis('())') => false
validateparenthesis(')(') => false
*/

function validateparenthesis(text) {
  const stack = [];

  for (const character of text) {
    if (character === '(') {
      stack.push(character)
    }

    if (character === ')') {
      if (!stack.length) {
        return false;
      }

      stack.pop();
    }
  }

  return !stack.length;
}

test(validateparenthesis('(((())()))'), true);
test(validateparenthesis('())'), false);
test(validateparenthesis(')('), false);

Шаг 7

Кажется, что для решения задачи в текущей постановке гораздо проще использовать счётчики, и это действительно так. Однако решение через счётчик будет работать только с одним видом скобок. Что если мы хотим также валидировать ещё и строки вида ([)]? Тогда можно доделать наше решение со стеком под работу с различными скобками. Учитывая, что из стека мы всегда будем доставать самую последнюю встретившуюся открывающую скобку, мы легко сможем проверить, подходят ли скобки друг другу. А ещё плюс такого решения в том, что мы не просто можем масштабировать его на новые скобки, а можем и кавычки туда воткнуть! Например, для строчки [()) мы сначала встретим [ и положим её в стек. Потом положим туда же ( — в стеке окажется ['[', '(']. Затем встретим закрывающую скобку. Достанем из стека последнюю попавшуюся нам скобку ( и увидим, ага, () формируют парные скобки. Идём дальше, встречаем ещё скобку ) и опять достаём скобку из стека — [. [) — непарные скобки, а значит, и строка построена неправильно, возвращаем false.

 import {test} from "./tester"

/*
Примеры:
validateparenthesis('(((())()))') => true
validateparenthesis('())') => false
validateparenthesis(')(') => false
validateparenthesis('([])') => true
validateparenthesis('([)]') => false
*/

const parantesisPairs = {
  '(': ')',
  '[': ']',
};

// А для более быстрой проверки, является ли символ нужной нам скобкой, можем заиспользовать уже знакомый Set!
const openingParenthesis = new Set(Object.keys(parantesisPairs));
const closingParenthesis = new Set(Object.values(parantesisPairs));

function validateparenthesis(text) {
  const stack = [];

  for (const character of text) {
    if (openingParenthesis.has(character)) {
      stack.push(character)
    }

    if (closingParenthesis.has(character)) {
      if (!stack.length) {
        return false;
      }

      const parenthesis = stack.pop();

      if (character !== parantesisPairs[parenthesis]) { // Если наша скобка — не закрывающая текущей открывающей
        return false;
      }
    }
  }

  return !stack.length;
}

test(validateparenthesis('(((())()))'), true);
test(validateparenthesis('())'), false);
test(validateparenthesis(')('), false);
test(validateparenthesis('([])'), true);
test(validateparenthesis('([)]'), false);

File tester.js

const results = document.getElementById('results')

export function test(left, right) {
  const result = document.createElement('li');

  if (left === right) {
    result.innerHTML = "Тест пройден!";
    result.style.color = "green";
  } else {
    result.innerHTML = `Тест не пройден! ${left} не равно ${right}`;
    result.style.color = "red";
  }

  results.appendChild(result);
}