Как написать функцию, которая распознает несбалансированные скобки

Question

Я пытаюсь написать функцию, которая проверяет правильность синтаксиса или нет. Если он верен, он возвращает 'ok', иначе он возвращает индекс ошибки. Пока мой код работает, если он правильный, если ошибка находится в первом или последнем индексе. Поиск ошибок между ними - это то, что я нахожу трудным. Вот мой код.

function syntaxError(syntax) {

  let arr = syntax.split('').join()
  let arr1 = [];
  let arr2 = [];
  let result;

  //Error if the first index contain a closing braces

  if (arr[0] === '>' || arr[0] === ']' || arr[0] === '}' || arr[0] === ')') {
    result = 0
  };

  if (arr === "") {
    result = 'ok'
  };

  //Error if its just a single brace

  if (arr.length === 1) {
    result = 0
  };

  //Error if the last index contain an opening braces

  if (arr.slice(-1) === '<' || arr.slice(-1) === '[' || arr.slice(-1) === '{' || arr.slice(-1) === '(') {
    result = indexOf(arr.slice(-1))
  };

  let char = arr[i];

  if (char == '[' || char == '{' || char == '<' || char == '(') {
    arr1.push(char)
  } else {
    arr2.push(char);
  }

  if (arr1.length === 0 || arr2.length === 0) {
    result = 0
  }

  if (arr1.length === arr2.length) {
    result = 'ok'

  }

  return result
}

В приведенном ниже примере должно возвращаться 95

('[[[[[[[[[[[[[[]]]]]]]]<<<<<<<<<<<>>>>>>>>>>>]]]]]]'+'[[[[[[[[[[[[[[]]]]]]]

<<<<<<<<<<<>>>>>>>>>>>]}]]]]' + '>')

Answer 1

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

Если завершено, и в стеке нет элемента, синтаксис в порядке, в противном случае возвращаетиндекс или индекс последнего нажатого открывающего символа.

Пример:

code        comment
----------- ---------------------------
[][[[]][][]
[]          balanced
  [         error, this returns later 2
   [[]]     balanced
       []   balanced
         [] balanced
            finally a missing ]

function syntaxError(syntax) {
    const
        isOpening = c => /[<[{(]/.test(c),
        isClosing = c => /[>\]})]/.test(c),
        open = { '>': '<', ']': '[', '}': '{', ')': '(' };

    var stack = [],
        index,
        finished = Array
            .from(syntax)
            .every((c, i) => {
                var temp = stack[stack.length - 1];
                if (isOpening(c)) {
                    if (temp && temp.c === c) {
                        temp.indices.push(i);
                    } else {
                        stack.push({ c, indices: [i] });
                    }
                    return true;
                }
                if (isClosing(c)) {
                    if (temp && temp.c === open[c]) {
                        temp.indices.pop();
                        if (!temp.indices.length) stack.pop();
                    } else {
                       index = stack.length ? stack.pop().indices.pop() : i;
                       return false;
                    }
                }
                return true;
            });

    return finished && !stack.length
        ? 'ok'
        : index === undefined
            ? stack.pop().indices.pop()
            : index;
}

console.log(syntaxError('[][][[{}]]'));  // ok

console.log(syntaxError(')'));
//                       0

console.log(syntaxError('[][][[{<}]]'));
//                       01234567

console.log(syntaxError('[][[[]][][]'));
//                       012

console.log(syntaxError('[[[[[[[[[[[[[[]]]]]]]]<<<<<<<<<<<>>>>>>>>>>>]]]]]]'+'[[[[[[[[[[[[[[]]]]]]]<<<<<<<<<<<>>>>>>>>>>>]}]]]]' + '>'));

Answer 2

Алгоритм для этого состоит в том, чтобы найти открывающий символ, поместить его в стек (или массив, что угодно). Найдите другой открывающий символ, поместите его в стек. Найдите закрывающий символ, который соответствует вершине стека, вытолкните открывающий символ из стека. Найдите закрывающий символ, который не соответствует вершине стека, вы нашли ошибку. Найдите закрывающий символ, и в стеке ничего нет, вы нашли ошибку. Добравшись до конца и сохранив все символы в стеке, вы обнаружили ошибку.