5

Помогите с примером: необходимо вернуть true если скобки совпадают, или false если нет. Набор скобок такой: ()[]{}

Например

text with([brackets]) true 
text with ([wrong brackets)] false

6
  • Что Вы уже делали? Покажите свой код
    – Mihanik71
    Commented 25 июл. 2016 в 7:29
  • Что значит "совпадают"?
    – user207618
    Commented 25 июл. 2016 в 7:29
  • Нет не делал, просто видел такой вопрос на одном из тестов для JS-разработчиков. Если бы был код, то конечно опубликовал, его нет. Commented 25 июл. 2016 в 7:31
  • 7
    решается с помощью структуры "стек" за O(n).... ideone.com/VTB1QI вот пример на паскале (старые добрые школьные времена).
    – pavel
    Commented 25 июл. 2016 в 7:36
  • @pavel, Runtime error 2 at $0804821D $0804821D что-то не так? а, это по умолчанию stdin пустой
    – Grundy
    Commented 25 июл. 2016 в 7:53

5 ответов 5

14

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

(Это особенно важно, если речь идет о собеседовании.)

Суть его заключается в обходе строки и поиске "несбалансированных" скобок с использованием стека. Алгоритм имеет вид:

  1. Выбираем первый символ строки
  2. Если это открывающая скобка - помещаем ее в стек
  3. Если это закрывающая скобка, извлекаем последнее значение из стека и проверяем скобки на соответствие. Если стек пуст или закрывающая скобка не соответствует открывающей - прерываем выполнение и возвращаем false
  4. Переходим к следующему символу строки и повторяем действия с п.2
  5. Если по окончании выполнения алгоритма стек не пуст (это возможно, если открывающих скобок больше, чем закрывающих) - возвращаем false.

Реализация на JavaScript может иметь вид:

var test = function(str) {
    var chars = str.split(''),
        stack = [],
        open = ['{', '(', '['],
        close = ['}', ')', ']'],
        closeIndex,
        openIndex;

    // Проходимся по строке, проверяя каждый ее символ (п.4).
    for (var i = 0, len = chars.length; i < len; i++) {
       openIndex = open.indexOf(chars[i]);
       if (openIndex !== -1) {
           // Нашли открывающую скобку. Помещаем ее в стек (п.2).
           stack.push(openIndex);
           continue;
       }

       closeIndex = close.indexOf(chars[i]);
       if (closeIndex !== -1) {
           // Нашли закрывающую скобку. Проверяем ее соответствие открывающей (п.3).
           openIndex = stack.pop();
           if (closeIndex !== openIndex) {
               return false;
           }
       }
    }

    // Проверяем дисбаланс открытых/закрытых скобок (п.5).
    if (stack.length !== 0) {
        return false;
    }

    return true;
}

Проверить этот код можно вот на таких примерах:

console.log(test('text with([brackets])')); // true
console.log(test('text with ([wrong brackets)]')); // false
console.log(test('text with [wrong brackets')); // false

А вот и рабочий пример на JSFiddle.

1
  • 1
    спасибо, очень полезно. Commented 25 июл. 2016 в 12:26
6

Ну как-то так:

/**
 * Проверяем корректный порядок скобок в строке
 *
 * @param {String} exp Строка с скобками для проверки
 *
 * @return {Boolean}
 */
function test(exp){
  // Если передали не строку - выходим
  if(typeof exp !== 'string')
    return false;

  let stack = [],
      // Сюда можно добавлять свои скобки: ключ - открываемая, значение - закрываемая
      brackets = {'(': ')', '{': '}', '[': ']'},
      openRegExp = [],
      closeRegExp = [],
      str = exp;
  
  // Создаём регулярные выражения для поиска
  Object.keys(brackets).forEach(e => openRegExp.push(`\\${e}`));
  openRegExp = new RegExp(openRegExp.join('|'));
  for(let i in brackets) if(brackets.hasOwnProperty(i)) closeRegExp.push(`\\${brackets[i]}`);
  closeRegExp = new RegExp(closeRegExp.join('|'));
  
  // Добавляем все найденные открывающие скобки в стёк
  while((tmp = openRegExp.exec(str)) && (str = str.substr(++tmp.index))) stack.push(tmp[0]);
  
  str = exp;

  // Если нашли какую-то закрывающую скобку
  while((tmp = closeRegExp.exec(str)) && (str = str.substr(++tmp.index)))
    // То проверяем: Или закончился стёк, а закрывающие скобки всё прибывают
    // Или является ли найденная скобка парой к открывающей скобке в конце стёка (самой глубокой)
    if(!stack.length || brackets[stack.pop()] !== tmp[0]) return false;
  
  // Всё ОК
  return true;
}


[
  `text with([brackets]) true`,
  `text with ([wrong brackets)] false`,
  `()[]{}()sdgsdg(sdg((((sg))))))(([[{sds}]]))`
].forEach(t => console.info(t, test(t)));

6
  • Other, спасибо )) Commented 25 июл. 2016 в 8:51
  • 1
    @MikhailZhuykov, пожалуйста!
    – user207618
    Commented 25 июл. 2016 в 8:51
  • @Other, зачем вам регулярные выражения? Задача решается через стек в один проход строки. Commented 25 июл. 2016 в 11:08
  • @DmitriySimushev, для наглядности.
    – user207618
    Commented 25 июл. 2016 в 15:20
  • @Other, и вы действительно считаете, что ваш ответ с регулярными выражениями нагляднее моего, без них? =) Commented 25 июл. 2016 в 16:06
0

Попробовал сам, вот что получилось:

var input = document.querySelector('#input'),
    output = document.querySelector('#output');

input.addEventListener('keydown', update);
input.addEventListener('keyup', update);
input.addEventListener('change', update);

function update () {
    var errorMessage;
    
    try {
        balanced.matches({source: input.value, open: ['{', '(', '['], close: ['}', ')', ']'], balance: true, exceptions: true});
    } catch (error) {
        errorMessage = error.message;
    }
    
    input.style.border = '10px solid ' + (errorMessage ? 'red' : 'green');
    output.innerHTML = errorMessage || '';
}
update();
body {
    background: #333;
    font-family: arial;
}
#input {
    outline: none;
}
#output {
    color: grey;
}
<script src="https://rawgit.com/icodeforlove/node-balanced/master/dist/balanced-min.js"></script>
<textarea id="input" cols="75" rows="10">((([])))</textarea>
<pre id="output"></pre>

2
  • 1
    вы думаете что обфусцированный код https://rawgit.com/icodeforlove/node-balanced/master/dist/balanced-min.js это то что поможет кому-то ещё решить задачу?
    – pavel
    Commented 25 июл. 2016 в 8:14
  • Нет, но есть живой пример...дальше по пути изучения... Commented 25 июл. 2016 в 8:16
0
function validBraces(braces){
  braces = braces.replace(/[a-zа-яё0-9]/gi, '')
  while(/\(\)|\[\]|\{\}/g.test(braces)){braces = braces.replace(/\(\)|\[\]|\{\}/g,"")}
  return !braces.length;
 }

Пробегаем циклом while по строке пока вхождения в соответствии с регулярным выражением не закончатся, на каждом цикле с помощью replace заменяем найденные вхождения на пустую строку. Возвращаем длину того что осталось в булевом виде.

3
  • 1
    в текущем виде это не будет работать на строках указанных в вопросе
    – Grundy
    Commented 27 дек. 2022 в 21:03
  • В текущем виде ваш ответ непонятен. Пожалуйста, нажмите править под сообщением, чтобы добавить больше подробностей, которые помогут другим понять, как он отвечает на заданный вопрос. Вы можете найти больше информации о том, как писать хорошие ответы в Справке. Commented 27 дек. 2022 в 21:04
  • Добавил регулярное выражение вырезающее всё кроме скобок. Проверил на строках в вопросе все работает корректно.
    – Max
    Commented 29 дек. 2022 в 0:12
-1

Два варианта решения. Но думаю должно быть более элегантное решение.

Вариант с рекурсией:

function verify(string, i = 0, filtered = []) {
  var rules = { '[': ']', '(': ')', '<': '>' };

  if (~Object.keys(rules).indexOf(string[i])) {
    filtered.push(string[i]);
  }

  if (~Object.values(rules).indexOf(string[i])) {
    if (rules[filtered[filtered.length - 1]] !== string[i]) {
      return false;
    }

    if (rules[filtered[filtered.length - 1]] === string[i]) {
      filtered.length = --filtered.length;
    }
  }

  return i !== string.length ? verify(string, ++i, filtered): true;
}

Вариант с циклом:

function verify(string) {
  var rules = { '[': ']', '(': ')', '<': '>' };

  var result = string.split('').reduce(function (acc, curr) {

  if (~Object.keys(rules).indexOf(curr)) {
    acc.push(curr)
  }

  if (~Object.values(rules).indexOf(curr) && rules[acc[acc.length - 1]] === curr) {
    acc.length = --acc.length;
  }

  return acc;
  }, []);

  return !Boolean(result.length);
} 

Ваш ответ

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

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