Рекурсивная валидация

[y0uix]

Здравствуйте!

Стоит задача валидировать вложенные скобки (({[) произвольной глубины вложенности. Причем может быть и так ({})[({})], это также валидный формат.

Написал:

function validBraces(braces) {
  if (braces.length % 2 !== 0) {
    return false;
  }
  
  var assoc = {
    '(': ')',
    '{': '}',
    '[': ']'
  };

  for (var i = 0, m; i < Math.round(braces.length / 2); i += 1) {
    if (!~Object.keys(assoc).indexOf(braces[i])) continue;
    m = braces.match(RegExp('\\' + braces[i] + '(' + (braces[i] === braces[i + 1] ? '.' : '[^\\' + assoc[braces[i]] + ']') + '*)\\' + assoc[braces[i]]));
    if (m === null || m[1].length % 2 !== 0) return false;
  }
  return true;
}

Он корректно мэтчит ({})[({})], но некорректно (({{[[]]}})), причем во многих других случаях также корректно отрабатывает.

Подскажите пожалуйста, где я не прав и как бы вы реализовали задачу? Спасибо.

[y0uix]

for (var i = 0, m; i < Math.round(braces.length / 2); i += 1)

Math.round тут излишне конечно. Идея собственно в том, чтобы мэтчить крайние символы-пары, а внутренность сперва проверять на четное количество скобок.

[danik.js]

Зачем там вообще регулярки - я не пойму? Пройди посимвольно и складывай в стек открывающие скобки, извлекай закрывающие. Если в стеке неподходящего вида скобка - значит ошибка. Если в конце стек не опустел - тоже ошибка.

[рони]

y0uix,
Баланс открывающихся и закрывающихся скобок.Стеки в JS

[nerv_]

y0uix,

console.log(isValid('({})[({})]'));
console.log(isValid('(({{[[]]}}))'));
console.log(isValid('({})[({})]'));


function isValid(string) {
    var regexp = /(?:\(.*?\)|\[.*?\]|\{.*?\})/;
    var replacementFn = function(line) {
        return line.slice(1, -1);
    };

    while (regexp.test(string)) {
        string = string.replace(regexp, replacementFn);
    }

    return !string.length;
}

Но, на первый взгляд, это не будет корректно работать потому, что надо делать так, как написал danik.js

[y0uix]

Спасибо всем огромное, самый мощный анклав JS-ниндзя, который я встречал.

Вот два решения:

function validBraces(braces) {
  var assoc = {
    '(': ')',
    '{': '}',
    '[': ']'
  },
  stack = [],
  char,
  len,
  i;

  for (i = 0, len = braces.length; i < len; i += 1) {
    char = braces[i];
    if (assoc[char]) {
      stack.push(char);
    } else {
      if (char !== assoc[stack.pop()]) {
        return false;
      }
    }
  }

  return !stack.length;
}

function validBraces(braces) {
  var pattern = /\(\)|\{\}|\[\]/g;
  while (pattern.test(braces)) {
    braces = braces.replace(pattern, '');
  }
  return !braces.length;
}