2

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

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

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

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

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;

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

2
  • 7
    Зачем так сложно? просто бегишь по строке и считаешь. Открывающая - плюс один, закрывающая - минус один, если вдруг сумма минус один - косая строка, дальше можно не смотреть, если в итоге не ноль - косая строка. Всё...
    – Akina
    9 окт 2018 в 5:22
  • Когда то я сделал это на php так: bitbucket.org/num8er/gsm-tasks/src/master/public/… методом стека
    – num8er
    29 мая 2019 в 22:30

8 ответов 8

2

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

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

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

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

9
  • 1
    Как только речь зайдет о нескольких типах скобок одновременно, потребуется алгоритм требующий дополнительной памяти (стека). Не обязательно. Своя переменная под каждый тип скобок, и разрешение на закрывающую скобку другого типа (смена типа по сравнению с предыдущей скобкой), только если для текущего типа сумма стала нулевой.
    – Akina
    9 окт 2018 в 5:46
  • @Akina: Не понял. Вот в этом случае ([{}]) где происходит "смена типа по сравнению с предыдущей скобкой"? 9 окт 2018 в 6:12
  • Первая скобка: cnt'()'=1, curr='()'. Вторая скобка: cnt'[]'=1, curr='[]'. Третья скобка: cnt'{}'=1, curr='{}'. Четвёртая скобка: закрывающая, тип совпадает с curr - допустимо, cnt'{}'=0, curr=null (если бы счётчик стал не ноль, тип остался бы curr='{}'). Пятая скобка: закрывающая, curr не ограничивает - допустимо, cnt'[]'=0, curr=null. Шестая скобка: закрывающая, curr не ограничивает - допустимо, cnt'()'=0, curr=null. Конец разбора, все счётчики нулевые, строка валидна.
    – Akina
    9 окт 2018 в 6:24
  • Вот так вот просто? Ну а теперь, пожалуйста, разберите [({}]). Каким образом ваш алгоритм "без памяти о прошлом" сможет отличить правильное ([{}]) от неправильного [({}])? 9 окт 2018 в 6:41
  • @Akina стек обязателен для нескольких типов скобок (кроме хитрого варианта с заменой, который требует ещё больше памяти). напишите ответ с кодом "без стека", я легко подберу, контрпример. Это стандартная задача с собеседований, её регулярно кто-то без стека порывается решить :)
    – user177221
    9 окт 2018 в 6:42
2

Можно дополнить код от PashaPash , чтобы он работал со всеми видами скобок:

const areBracketsBalanced = str => {
  let prev = '';
  let replaced = str;
  const reg = /\(\)|\[\]|\{\}/gm;

  while (replaced !== prev) {
    prev = replaced,
    replaced = replaced.replace(reg, '');
  }

  return prev == '';
}

// tests
const str1 = '(())';
const str2 = '(()))';
const str3 = '()()()()';
const str4 = '(()()))';
const str5 = '(){[()()]}()()'

const arr = [str1, str2, str3, str4, str5];
arr.forEach(item => {
  const result = areBracketsBalanced(item);
  console.log(item, result);
})

1

Вроде все работает

const str1 = '(())';
const str2 = '(()))';
const str3 = '()()()()';
const str4 = '(()()))';

function checkBrackets(str = '') {
  if (str === '') return true;
  const right = /\(/gi;
  const left = /\)/gi;
  let numLeft = str.match(left);
  let numRight = str.match(right);
  if ((!numLeft || !numRight) || numLeft.length !== numRight.length) return false;
  right.lastIndex = 0;
  left.lastIndex = 0;
  const {
    length
  } = str;
  const firstHalf = str.substr(0, length / 2);
  const secondHalf = str.substr(length / 2);
  numLeft = firstHalf.match(right);
  numRight = secondHalf.match(left);
  if ((!numLeft || !numRight) || numLeft.length > numRight.length) return false;
  return true;
}

const arr = [str1, str2, str3, str4];
arr.forEach(item => {
  const result = checkBrackets(item);
  console.log(item, result);
})

1

Раз подняли вопрос, то вот решение без стека:

const areBracketsBalanced = str => {
  let prev = '';
  for (let replaced = str; replaced != prev; prev = replaced, replaced = replaced.replace('()', ''));
  return prev == '';
}

const str1 = '(())';
const str2 = '(()))';
const str3 = '()()()()';
const str4 = '(()()))';

const arr = [str1, str2, str3, str4];
arr.forEach(item => {
  const result = areBracketsBalanced(item);
  console.log(item, result);
})

0
fn bracket_balance(string s) {
  stack st
  for (i = 0; i < s.len; i++) {
    switch (s[i]) {
    case '(':
    case '[':
    case '{':
      st.push(st[i])
      break
    case ')':
      if (st.size > 0 and st.top() == '(')
        st.pop()
      else
        return false
      break
    case ']':
      if (st.size > 0 and st.top() == '[')
        st.pop()
      else
        return false
      break
    case '}':
      if (st.size > 0 and st.top() == '{')
        st.pop()
      else
        return false
      break
    }
  }
  if (st.size > 0)
    return false
  return true
}
1
  • добро пожаловать на Stack Overflow на русском! пожалуйста, постарайтесь оставлять чуть более развёрнутые ответы. дополнить ответ можно, нажав править 25 янв 2020 в 18:14
0

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

<?php

function checkBrackets($sString = null)
{
    
    //первая проверка на то, что данные были переданы, и строка не пустая
    if(is_null($sString) || $sString == '')
        return true;
    
    $sString = str_split($sString);
    //инициализируем скобки которые будем проверять    
    $aSkobki = ['(' => ')', '[' => ']'];
    
    //получаем длину строки для её обхода.
    $iLength = count($sString);
    if ( $iLength % 2 != 0) {
        throw new Exception ('Строка не может быть сбалансирована, т.к. кол-во элементов не парное');  
    }
    $sSkobki = [];
    foreach ($sString as $key => $value) {
        //Если наша скобка открывающаяся, нужно просто добавить элемент массива в наш стек.
        if (array_key_exists($value, $aSkobki)) {
            $sSkobki []= $value;
            continue;
        }
        //Если наша скобка закрывающаяся, нужно проверить, соответствует ли она значениям нашего проверяющего массива
        elseif (in_array($value, $aSkobki)) {
        //Нужно проверить на данной итерации цикла, соответствует ли последний элемент "стека" ключу значения нашей закр-ся скобки
        //Для этого найдем какая должна быть откр-ся скобка для данной закрывающейся см. '(' => ')', '[' => ']'
        //Если последний элемент "стека" совпадает с ключом нашего проверяющего значения, удалим последний элемент "стека"
            if (end($sSkobki) == array_search($value, $aSkobki)) {
                array_pop($sSkobki);
            }
            else {
                throw new Exception ('Строка не сбалансированна, т.к. обнаружено не парнок закрытие скобок');
            }
        }
        else {
            throw new Exception ('Строка не может быть сбалансирована, т.к. начинается с закрывающейся скобки');
        }
    }

    //Конечная проверка на не пустой "стек"
    if (empty($sSkobki)) {
        return "Строка сбалансированна";
    }
    else{
        return "Строка не сбалансированна";
    }

}

echo checkBrackets('([]()())()[]([))');

?>
1
  • Добавить можно и фигурные скобки, просто вписав в массив проверочный ключ и значение этих скобок. Думаю так же можно сделать и с тегами, нагрузив регуляркой <pre> </pre> проверку на слеш перед символами тега. Достаточно интересное задание кстати) 5 янв 2021 в 11:01
0
const checkIsBalanced = (expression) => {
  // Инициализация стека
  const stack = [];
  // Проходим по каждому символу в строке 
  for (const symbol of expression) {
    // Смотрим открывающий или закрывающий
    if (symbol === '(') {
      stack.push(symbol);
    } else if (symbol === ')') {
      // Если для закрывающего не нашлось открывающего, значит баланса нет
      if (!stack.pop()) {
        return false;
      }
    }
  }

  return stack.length === 0;
};
-1

function balancer(v) {
    let store1 = []
    let store2 = []
    let flag = false

    if (v) {
        for (let i = 0; i <= v.length - 1; i++) {
            if (v[i] === '[' || v[i] === '(' || v[i] === '{') {
                store1.push(v[i])
                continue
            }

            if (v[i] === ']' || v[i] === ')' || v[i] === '}') {

                if (store1.length === 0) {
                    flag = false
                    break
                }

                store2.push(v[i])

                if (store2.length > store1.length) {
                    flag = false
                } else {
                    if (store2[store2.length - 1] === ')') {
                        if (store1[store1.length - store2.length] === '(') {
                            flag = true
                        } else {
                            flag = false
                        }
                    }

                    if (store2[store2.length - 1] === '}') {
                        if (store1[store1.length - store2.length] === '{') {
                            flag = true
                        } else {
                            flag = false
                        }
                    }

                    if (store2[store2.length - 1] === ']') {
                        if (store1[store1.length - store2.length] === '[') {
                            flag = true
                        } else {
                            flag = false
                        }
                    }
                }
            }
        }
    } else {
        return false
    }

    return flag
}

console.log(balancer('{([])}'))
console.log(balancer('{}}'))
console.log(balancer('}}'))
console.log(balancer('{)'))
console.log(balancer('{[}'))
console.log(balancer('{sdc[sdc}'))
console.log(balancer(''))

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.