баланс скобок, если встречаются одинаковые, js

Question

const config1 = [['(', ')']];
const config2 = [['|', '|']];
const config3 = [['(', ')'], ['|', '|']];
const config4 = [['(', ')'], ['[', ']'], ['{', '}'], ['|', '|']];

const check = (str, bracketsConfig) => {
  const openBrack = [];
  const arrOpen = bracketsConfig.toString().split(',');
  for (let i = 0; i < arrOpen.length; i += 2) {
    openBrack.push(arrOpen[i]);
  }

  let pairsBrack = {};
  pairsBrack = Object.fromEntries((bracketsConfig).map(
    ([key, value]) => [value, key]
  ));

  let stack1 = [];
  for (let i = 0; i < str.length; i++) {
    let currentSymbol = str[i];
    let topElement = stack1[stack1.length - 1];

    if (openBrack.includes(currentSymbol)) {
      stack1.push(currentSymbol);
    } else {
      if (stack1.length === 0) { return false; }

      if (pairsBrack[currentSymbol] === topElement) {
        stack1.pop();
      } else {
        return false;
      }
    }
    if (stack1[i] == stack1[i + 1]) {
      stack1.pop();
      stack1.pop();
    }
  }
  return (stack1.length === 0);
}

// Примеры: 
let str = '|()|(||)||'; 
let bracketsConfig = [['(', ')'], ['|', '|']];
console.log(check(str, bracketsConfig));  // true 

str = '||'; 
bracketsConfig = [['|', '|']];
console.log(check(str, bracketsConfig));  // true 

str = '|(|)'; 
bracketsConfig = [['(', ')'], ['|', '|']];
console.log(check(str, bracketsConfig));  // false

такой код работает для определения соответствуют ли скобки в строках '()', но не для '||' или '|(|)'.
В чем ошибка моя?

Примеры (они есть и в коде):

Входные данные для
```
str = '|()|(||)||'; 
bracketsConfig = [['(', ')'], ['|', '|']];  
```
Результат (check(str, bracketsConfig)) вернет true
Входные данные для
```
str = '||'; 
bracketsConfig = [['|', '|']];  
```
Результат (check(str, bracketsConfig)) вернет true
Входные данные для
```
str = '|(|)'; 
bracketsConfig = [['(', ')'], ['|', '|']]; 
```
Результат (check(str, bracketsConfig)) вернет false

Answer 1

Приведенный алгоритм плохо подходит для случая, когда открывающая и закрывающая скобки одинаковые.

В этом случае из-за проверки if (openBrack.includes(currentSymbol)) { такие скобки всегда будут добавляться в стек, независимо от того, закрывающая она или открывающая.

Для случая, когда открывающая и закрывающая скобки могут совпадать проще воспользоваться рекурсивным алгоритмом.

Логика простая:

получаем открывающую скобку
если следующий символ - закрывающая - пара получилась
если нет - получаем внутреннюю пару.

Если на каком-то из шагов не получилось получить пару - вся цепочка невалидная.

Пример реализации:

const config1 = [
  ['(', ')']
];
const config2 = [
  ['|', '|']
];
const config3 = [
  ['(', ')'],
  ['|', '|']
];
const config4 = [
  ['(', ')'],
  ['[', ']'],
  ['{', '}'],
  ['|', '|']
];

const check = (str, bracketsConfig) => {
  let pairsBrack = Object.fromEntries(bracketsConfig); // карта скобок

  function getPair() {
    if (i >= str.length) return false;
    const close = pairsBrack[str[i]]; // получаем закрывающую скобку
    if (!close) return false; // если не нашли - значит текущий символ не открывающая скобка - и это возможно только в случае невалидной строки
    for (i = i + 1; i < str.length; i++) {
      if (str[i] === close) return true; // если текущий символ закрывающая скобка - значит пара закрылась
      if (!getPair()) return false; // если нет - проверяем внутреннюю пару
    }
    return false; // если не нашли закрывающую скобку - возвращаем false
  }

  for (var i = 0; i < str.length; i++) {
    if (!getPair()) return false; // если не получили пару - возвращаем false
  }
  return true; // если все пары разобрались - возвращаем true
}

// Примеры: 
let str = '|()()|(||)||';
let bracketsConfig = [
  ['(', ')'],
  ['|', '|']
];
console.log(check(str, bracketsConfig)); // true 

str = '||';
bracketsConfig = [
  ['|', '|']
];
console.log(check(str, bracketsConfig)); // true 

str = '|(|)';
bracketsConfig = [
  ['(', ')'],
  ['|', '|']
];
console.log(check(str, bracketsConfig)); // false

Answer 2

Есть более элегантное решение (не мое), когда убираем из строки парные скобки из конфига. Если строка после нескольких итераций обнулилась, возвращаем true, в противном случае false.

function check(str, bracketsConfig) {
  const parsedBracketsConfig = bracketsConfig.map((item) => {
    return `${item[0]}${item[1]}`;
  });

  let prevLength = str.length;

  while (str.length) {
    parsedBracketsConfig.forEach((item) => {
      str = str.replaceAll(item, "");
    });

    if (str.length === prevLength) {
      return false;
    }

    prevLength = str.length;
  }

  return true;
}

console.log(check("()", [["(", ")"]]), true); // -> true
console.log(check("((()))()", [["(", ")"]]), true); // -> true
console.log(check("())(", [["(", ")"]]), false); // -> false
console.log(check("([{}])", [["(", ")"], ["[", "]"], ["{", "}"]]), true); // -> true
console.log(check("[(])", [["(", ")"], ["[", "]"]]), false); // -> false
console.log(check("[]()", [["(", ")"], ["[", "]"]]), true); // -> true
console.log(check("[]()(", [["(", ")"], ["[", "]"]]), false); // -> false

// special case: opening and closing bracket can be the same :)

console.log(check("||", [["|", "|"]]), true); // -> true
console.log(check("|()|", [["(", ")"], ["|", "|"]]), true); // -> true
console.log(check("|(|)", [["(", ")"], ["|", "|"]]), false); // -> false
console.log(check("|()|(||)||", [["(", ")"], ["|", "|"]]), true); // -> true
console.log(check("|(||||(||)||)|", [["(", ")"], ["|", "|"]]), true); // -> true

БЛОГ НА HUSL

баланс скобок, если встречаются одинаковые, js

Ответы (2 шт):