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

[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,
http://javascript.ru/forum/css-html/34223-balans-otkryvayushhikhsya-i-zakryvayushhikhsya-skobok-steki-v-js.html

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