Как проверить скобки в строке?

Question

[yura_born]

Помогите плз. разобраться
Функция которая показывает правильно ли закрыты раскрыты скобки 3-ий день мучаюсь. Вот мой код:

function check(str, bracketsConfig) {
  let resault = [];
  let resaultDouble = [];
  let itemPos;
  const strArr = str.split('');

  for(let i=0; i<strArr.length;){
    let item = strArr.shift();

    for(let k = 0; k<bracketsConfig.length; k++){
      itemPos = bracketsConfig[k].indexOf(item);

      if(itemPos === -1){
        continue;
      }
      // console.log(`itemPos = ${itemPos}`);

      if(k==0){
        if(itemPos %2 === 0){
          resault.push(itemPos +1)
        }
        else{
          if(resault.pop() !== itemPos) {
            continue;
          }
        }
      }else{
        if(itemPos %2 === 0){
          resaultDouble.push(itemPos +1)
        }
        else{
          if(resaultDouble.pop() !== itemPos) {
            continue;
          }
        }
      }

    }
  }

  // console.log(resault);



  if(resault > 0 || resaultDouble > 0){
    console.log('false');
  }
  else{
    console.log('true');
  }

  
}

check('()', [['(', ')']]) // -> true
check('((()))()', [['(', ')']]) // -> true
check('())(', [['(', ')']]) // -> false
check('([{}])', [['(', ')'], ['[', ']'], ['{', '}']]) // -> true
check('[(])', [['(', ')'], ['[', ']']]) // -> false
check('[]()', [['(', ')'], ['[', ']']]) // -> true
check('[]()(', [['(', ')'], ['[', ']']]) // -> false

Все отрабатывает нормально, кроме вот этой:

check('[(])', [['(', ')'], ['[', ']']]) // -> false

так как функция думает чтот все ок, массивы пришли пустые и мне она выдает true, а надо false

Answer 1

[Rsa97]

Такие задачи решаются через общий стек. При поступлении на вход открывающей скобки на стек кладётся соответствующая закрывающая скобка (или эквивалентный код). При поступлении закрывающей скобки снимается вершина стека и проверяется на совпадение с ней.

Например

function check(str, bracketsConfig) {
  let bconf = bracketsConfig.reduce(
    (acc, val) => {
      acc[val[0]] = val[1];
      acc[val[1]] = null;
      return acc;
    },
    {}
  );
  let stack = [];
  for (let i = 0; i < str.length; i++) {
    let char = str[i];
    if (bconf[char] === null) {
      if (stack.pop() !== char) {
        return false;
      }
    } else if (bconf[char] !== undefined) {
      stack.push(bconf[char]);
    }
  }
  if (stack.length !== 0) {
    return false;
  }
  return true;
}

Answer 2

[Stalker_RED]

Перебираем посимвольно, всего 4 правила:

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

Answer 3

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

Алгоритм, вроде бы, не вполне рабочий: рассматривает два возможных типа скобок и жёстко закодировал два варианта: две переменные под это – resault и resaultDouble.

Я бы предложил двигаться по строке и в единый массив складывать последовательность: «что сейчас открыто?».

В массив класть индекс того типа скобок, который открылся. В любой момент можно либо закрыть последнюю открытую скобку. Либо открыть ещё одну любую новую. Например:

// круглые скобки - индекс 0
// квадратные - индекс 1
// строка:
( ( [ ] [ ] ) )

// скобка - массив
( 0, 
( 0, 0
[ 0, 0, 1,
] 0, 0,
[ 0, 0, 1,
] 0, 0,
) 0,
) пустой массив

При закрывающей скобке проверять, её ли пара последняя в массиве. В конце должен остаться пустой массив.

spoiler

Answer 4

[gsaw]

Ну вроде все верно. У вас круглые и квадратные скобки в разных стэках копятся, то есть семантически разные. Круглые в resault и квадратные в resaultDouble. Оставьте один какой то, если скобки семантически одинаковы.