Задача на сбалансированность скобок

269
07 февраля 2019, 15:20

Условия задачи

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

Строка считается корректной (сбалансированной), если содержащаяся в ней скобочная структура соответствует требованиям:

Скобки — это парные структуры. У каждой открывающей скобки должна быть соответствующая ей закрывающая скобка.
Закрывающая скобка не должна идти впереди открывающей.

import areBracketsBalanced from 'roundBracketsValidator';

areBracketsBalanced('(())'); // true areBracketsBalanced('((())'); // false

Мое решение не проходит проверку. Пишет const str7 = '())(()';

37 | expect(areBracketsBalanced(str7)).toBe(false); Мой код ниже

const areBracketsBalanced = (str) => {
  let leftBrackets = '';
  let rightBrackets = '';
  switch(str[0]) {
    case ')':
      return false;
      break;
    case '':
      return true;
      break;
  };
  if (str[str.length - 1] === '(') {
    return false;
  };
  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(') {
      leftBrackets += str[i];
    } else if (str[i] === ')') {
      rightBrackets += str[i];
    }
  };
  if (leftBrackets.length === rightBrackets.length) {
    return true;
  } else {
    return false;
  }
};
export default areBracketsBalanced;

Что можно исправить?

Answer 1

Ваш алгоритм сильно перегружен ненужными действиями, но если вы все таки хотите реализовать проверку именно так - с накоплением строк leftBrackets и rightBrackets - то вам еще обязательно нужно следить, чтобы в процессе накопления этих строк rightBrackets.length никогда не превосходило leftBrackets.length. Это надо проверять именно в цикле накопления, а не после него. Если в какой-то момент выполнится rightBrackets.length > leftBrackets.length, то скобки не сбалансированы и дальнейшая проверка бессмысленна.

Дополнительные частные проверки, которые вы поставили перед циклом, совершенно не нужны и только усложняют код. Цикл сам прекрасно отловит эти нарушения.

Но на самом деле все это можно реализовать намного проще. Никаких строк накапливать не надо вообще. Нужно просто завести счетчик открытых скобок, который увеличивается на 1 для ( и уменьшается на 1 для ). Скобки являются сбалансированными если в процессе подсчета этот счетчик никогда не становился отрицательным и в конце подсчета он равен строго 0.

Такое простое решение возможно только для случая скобок одного типа. Как только речь зайдет о нескольких типах скобок одновременно, потребуется алгоритм требующий либо дополнительной памяти (стека), либо многопроходного/произвольного доступа к входной последовательности.

READ ALSO
Parallax, появление элементов при горизонтальном движении страницы

Parallax, появление элементов при горизонтальном движении страницы

Есть вот такой код, писал его самПроблема в том что у меня параллакс эффект который выводит страницу справа налево

195
Появление блока по клику на ссылку

Появление блока по клику на ссылку

Немного знаю Javascript и JqueryСтолкнулся с Angular 6 CLI

174
Работа с mouseenter и mouseleave

Работа с mouseenter и mouseleave

Есть проблемаВОт код:

208
createObjectURL is not a function Jest

createObjectURL is not a function Jest

Во время выполнения тестов на Jest, падает:

160