Help with an example: you must return true if the brackets match, or false if not. A set of brackets like this: ()[]{}

for example

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

  • What have you done? Show your code - Mihanik71
  • What does "match" mean? - user207618
  • No, I didn’t; I just saw such a question on one of the tests for JS developers. If there was a code, then of course I published it, it is not. - Fox
  • 6
    is solved using the stack structure for O (n) .... ideone.com/VTB1QI here is an example on pascal (good old school days). - pavel
  • @pavel, Runtime error 2 at $ 0804821D $ 0804821D something wrong? a, this is the default stdin empty - Grundy

3 answers 3

Well, something like this:

 /** * Проверяем корректный порядок скобок в строке * * @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)));

  • Other, thanks)) - Fox
  • one
    @MikhailZhuykov, please! - user207618
  • @Other, why do you need regular expressions? The problem is solved through the stack in one pass of the line. - Dmitriy Simushev
  • @DmitriySimushev, for clarity. - user207618
  • @Other, and do you really think that your answer with regular expressions is clearer than mine, without them? =) - Dmitriy Simushev

In spite of the fact that the answer has already been given (and marked as correct), there is a much simpler and more effective (from the point of view of computing resources) method of solving the problem.

(This is especially important when it comes to an interview.)

Its essence is to bypass the string and search for "unbalanced" brackets using the stack. The algorithm has the form:

  1. Select the first character of the string.
  2. If this is an opening bracket, we put it on the stack.
  3. If it is a closing parenthesis, retrieve the last value from the stack and check the parentheses for consistency. If the stack is empty or the closing bracket does not match the opening bracket, we interrupt the execution and return false
  4. Go to the next character of the line and repeat the actions from paragraph 2.
  5. If at the end of the algorithm execution the stack is not empty (this is possible, if there are more opening brackets than closing ones), then we return false .

The JavaScript implementation can be:

 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; }

You can check this code here with such examples:

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

And here is a working example on JSFiddle .

  • Thanks, very helpful. - Fox

I tried it myself, that's what happened:

 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>

  • one
    Do you think that the obfuscated code https://rawgit.com/icodeforlove/node-balanced/master/dist/balanced-min.js is that which will help someone else to solve the problem? - pavel
  • No, but there is a living example ... further along the path of learning ... - Fox