Можно ли этот пример упростить до одного регулярного выражения?

Question

[Вадим В]

Хочу найти более короткое и оптимизированное решение этой задачи. Эта функция проверяет, если текст обернут в скобки таких видов (), [], {}, то возвращает true, и возвращает false если вложенность неправильная

Например:

console.log(verify("a(b)")); //true
console.log(verify("[{}]")); //true
console.log(verify("[(]")); //false
console.log(verify("}{")); //false
console.log(verify("z([{}-()]{a})")); //true
console.log(verify("")); //true
console.log(verify("(((}")); //false

function verify(text) {
  text = text.replace(/[^\(\)\[\]\{\}]/g, ""); // оставит только символы [, ], (, ), {, }

  let prevText = "";
  while (text.length !== prevText.length) {
    prevText = text;

    text = text
      .replace("()", "")
      .replace("[]", "")
      .replace("{}", "");
  }

  return !text.length ? 1 : 0;
}

Comments

[RAX7]

В качестве оптимизации можно заменить:
1)

text = text
      .replace("()", "")
      .replace("[]", "")
      .replace("{}", "");

на
text = text.replace(/(\[\])|(\(\))|(\{\})/g, '')
2)
!text.length ? 1 : 0;
на
!text.length;
3) перед while проверить text.length на кратность двум. (если не кратно то сразу return false)

[Вадим В]

RAX7, По условиям задачи нужно возвращать 0 либо 1, поэтому 3 пункт не подходит. А 1 и второй пункты тоже не подходит под условия задачи, так как может быть вложенность одних кавычек в другие, и не обязательно будет text.length равен 2, как в этом случае console.log(verify("[{}]")); //true
Но в любом случае спасибо за помощь

[RAX7]

reyzele, если к примеру у тебя будет 7 скобок, то могут ли они быть парными. Кратность двум проверяй, а не равенство.

[Вадим В]

RAX7, А точно, извини, перепутал )

Answer 1

[Сергей Соколов]

Регулярные выражения «под капотом» не так легки, как выглядят. Там те же циклы, память.

Данную задачу можно решить посимвольным чтением с занесением открывающих скобок в буфер FILO (First In - Last Out, Первым вошёл, последним вышел). И изъятием из буфера, с хвоста, закрывающих. До первой ошибки или до конца строки. В любой момент открывающая скобка ОК, пушится в буфер. Закрывающая ОК только, если соотв. ей открывающая – последняя в буфере. И в конце убедиться, что буфер пуст - каждой открытой нашлась пара.

Решение, тесты проходит

function verify(text) {
  const buffer = [];
  const valid = '()[]{}';

  for (let i = 0, len = text.length; i < len; i++) {
    const c = text[i];
    const idx = valid.indexOf(c);
    if (-1 === idx) continue; // не скобка
    if (idx & 1) { // закрывающая (нечет)
      if (0 === buffer.length) return false;
      if (valid.indexOf(buffer.pop()) + 1 !== idx) return false;
    } else { // открывающая
      buffer.push(c);
    }
  }
  
  return buffer.length === 0;  
}

Тесты

(()=>{
const tests = [
  ["a(b)", true         ],
  ["[{}]", true         ],
  ["[(]", false         ],
  ["}{", false          ],
  ["z([{}-()]{a})", true],
  ["", true             ],
  ["(((}", false        ],
];

return JSON.stringify(
  tests.map(t => (verify(t[0]) === t[1] ? 'OK' : 'FAIL' ) + ': ' + t[0])
  , null,  
  2
);
})()


/*
[
  "OK: a(b)",
  "OK: [{}]",
  "OK: [(]",
  "OK: }{",
  "OK: z([{}-()]{a})",
  "OK: ",
  "OK: (((}"
]
*/

Comments

[Вадим В]

Спасибо друг за твою помощь и такой развернутый ответ

Answer 2

[Lynn «Кофеман»]

Нет.

В теории для это можно использовать рекурсивные регулярки, но в js их нет.
www.cyberforum.ru/post4793615.html