Рекурсивная валидация
Здравствуйте!
Стоит задача валидировать вложенные скобки (({[) произвольной глубины вложенности. Причем может быть и так ({})[({})], это также валидный формат. Написал: 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; } Он корректно мэтчит ({})[({})], но некорректно (({{[[]]}})), причем во многих других случаях также корректно отрабатывает. Подскажите пожалуйста, где я не прав и как бы вы реализовали задачу? Спасибо. |
for (var i = 0, m; i < Math.round(braces.length / 2); i += 1) Math.round тут излишне конечно. Идея собственно в том, чтобы мэтчить крайние символы-пары, а внутренность сперва проверять на четное количество скобок. |
Зачем там вообще регулярки - я не пойму? Пройди посимвольно и складывай в стек открывающие скобки, извлекай закрывающие. Если в стеке неподходящего вида скобка - значит ошибка. Если в конце стек не опустел - тоже ошибка.
|
|
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 |
Спасибо всем огромное, самый мощный анклав 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; } |
Часовой пояс GMT +3, время: 13:36. |