Сегодня я решу базовый вопрос алгоритма стека.
Вопрос ниже..

В. Создайте функцию для проверки правильности скобок или нет.
например) ‘()’ =› O, ‘(()’ =› X, ‘(())’=› O, ‘)()()’ =› X…

Это очень простой алгоритм стека. Давайте подумаем, что это игра на совпадения. Правильное соответствие: ‘()’. Нам нужно проверить три точки. 1) Есть ‘(’ и ‘)’. 2) «(» должно быть слева, а «)» должно быть справа. Чтобы проверить правильность данной строки в скобках, нам нужно подумать, какие случаи неверны.

Во-первых, если закрывающая скобка ")" стоит перед "(", результатом должно быть "X". Во-вторых, если остается только "(", результат должен быть "X".

Давайте представим, что у нас есть два вида деревянных блоков, которые имеют форму «(» и «)». Всего блоков 5. 3 из них «(» и 2 из них «)». Эти блоки помещаются в поле (col: 5 x row:1 ) в порядке '()(()'. Игра выглядит так. Если блоки '(' и ')' объединяются, мы можем завершить '( )", то мы можем удалить эти два блока. Если у нас нет блоков в последнюю минуту, мы выиграем игру. Но если мы поместим блок ')', если нет '(', игра окончена. и если мы остался только блок '(' без блока ')', игра также окончена.

Итак… Это означает, что ‘(’ является предметом сравнения, а ‘)’ является компаратором. Давайте помнить, что это вопрос стека. В алгоритме структуры данных стека есть несколько важных вещей для решения проблемы. StackArray/top/Push/Pop.

В этом случае мы можем поместить ‘(‘ внутри StackArray. Чтобы мы могли сравнить вершину (последний блок, который мы поместили) и ‘)’. Здесь важным моментом является то, что мы должны поместить '(' в массив стека по порядку. Поскольку эта игра заботится о порядке. Тогда как мы делаем это возможным? Используя push() в цикле For!
var stackArr = [] ; //создаем пустой массив стека. Мы собираемся заполнить этот пустой стек только '(', чтобы мы могли сравнивать всякий раз, когда у нас есть ')'

function solution(sample) {
  for (var i=0; i < sample.length; i++) { //we need to check every   element in sample array
   if (sample[i] === "(")) {
     stackArr.push("(")
   } 
...
 }

Но что, если мы нашли «)» во время цикла? затем пришло время сравнить с «верхней частью» массива стека. Здесь, если последним элементом массива стека является «(», мы можем объединить с «)» и завершить «()», тогда мы можем удалить эти два элемента. Тогда как мы удаляем? Использование pop()!
var stackArr = []; //создаем пустой массив стека. мы собираемся заполнить этот пустой стек только '(', чтобы мы могли сравнивать всякий раз, когда у нас есть ')'

function solution(sample) {
  for (var i=0; i < sample.length; i++) { //we need to check every element in sample array
   if (sample[i] === "(")) {
     stackArr.push("(")
   } else if (sample[i] === ")") {
     if (stackArr.length === 0) {
        return 'X'; //if you have ')' but stackArr doesn't have '(', stop this loop and return 'X' 
     } else { stackArr.pop() } //remove last '(' from stackArr
}
...
}

Кстати, мы должны быть осторожны, используя return внутри функции. Потому что, если интерпретатор javascript читает «return», он возвращает значение и сразу же останавливает функцию.

Итак, теперь мы почти завершили метод решения. Но мы не рассмотрели один случай, который является неправильным. if После проверки всех элементов у нас есть ‘(‘ в массиве стека, но нет ‘)’, поэтому мы не можем сравнивать. вар стекАрр = [];

function solution(sample) {
  for (var i=0; i < sample.length; i++) {
    if (sample[i] === "(")) {
      stackArr.push("(");
    } else if (sample[i] === ")") {
      if (stackArr.length === 0) {
        return 'X'; 
      } else { stackArr.pop() }
  }
 if (stackArr.length !== 0) {
   return 'X'; //As it means we have '(' but no ')'
 }
   return 'O'; //If sample passes all rules, return 'O'
}
solution(['(', ')','(']) => 'X' cuz only '(' left.
solution([')' '(', '(']) => 'x' cuz when we have ')' stackArr.length === 0.
solution(['(',')','(',')']) => 'O' YaY!

Хорошо! мы только что завершили функцию решения. Мы сделали два поведения. Один складывает массив стека с помощью ‘(‘, а другой сравнивает всякий раз, когда у нас есть ‘)’ и удаляет последний элемент в стекированном массиве. Это поведение происходит подряд, потому что стек — это линейная структура данных. В линейной структуре данных мы не можем выполнять некоторые действия одновременно. Стек имеет структуру LIFO (Last In, First Out). Мы можем вытащить только последний элемент из сложенного массива.

Просто чтобы вы знали, это алгоритм O (n). Потому что у него есть один цикл for, и этот цикл будет выполняться столько раз, сколько длина семпла.

Спасибо за чтение, и если вы обнаружили какие-либо неправильные моменты или если у вас есть лучшее решение, сообщите мне об этом :)