Skip to content

Instantly share code, notes, and snippets.

@saionaro
Created November 19, 2017 11:14
Show Gist options
  • Save saionaro/e02f9f7cc9388b38af123f2a86d9c5d6 to your computer and use it in GitHub Desktop.
Save saionaro/e02f9f7cc9388b38af123f2a86d9c5d6 to your computer and use it in GitHub Desktop.
42
const forCheck = [
'({(){}()})()', //true
'({(}){})', //false
'{(({}))}', // true
'{}{}(){}{}{}{}{}', // true
'{}{{}}{()}', // true
'({}{)})', // false
'))((' // false
];
const scobTypes = [
['(', ')'],
['{', '}']
];
/**
* Смотрим последний элемент стэка, не извлекая его
* @param {Array} stack Стэк
* @return {String}
*/
const getLast = stack =>
stack[stack.length - 1];
/**
* Проверяем, являются ли скобки правильной парой
* (одного типа, открывающия + закрывающая)
* @param {String} fst Первая скобка
* @param {String} scd Вторая скобка
* @return {Boolean}
*/
const isPair = (fst, scd) =>
scobTypes.some(item =>
item[0] === fst &&
item[1] === scd
);
/**
* Является ли скобка закрывающей
* @param {String} scob Скобка для проверки
* @return {Boolean}
*/
const isClosing = scob =>
scobTypes.some(item => item[1] === scob);
/**
* Проверяет не являются ли скобки "неправильной парой"
* (разного типа, открывающая + закрывающая)
* @param {String} fst Первая скобка
* @param {String} scd Вторая скобка
* @return {Boolean}
*/
const isFakePair = (fst, scd) =>
!isClosing(fst) &&
isClosing(scd);
/**
* Метод проверки скобочной последовательности на правильность
* @param {String} scobs Скобочная последовательность
* @return {Boolean}
*/
const check = scobs => {
let stack = [];
for(let i = 0; i < scobs.length; i++) {
// console.log(stack);
let char = scobs.charAt(i);
// console.log('Get scob: ' + char);
if(!stack.length) {
stack.push(char);
continue;
}
let lastSym = getLast(stack);
if(isPair(lastSym, char)) {
stack.pop();
/*
* Условие ниже нужно для ранней остановки цикла
* Если скобка на вершине стека и входящая скобка
* не пара, то если это открыающая + закрывающая скобка,
* то мы имеем заведомо неправильную последовательность,
* например: (}())
*/
} else if(isFakePair(lastSym, char)) {
return false;
} else {
stack.push(char);
}
}
return !stack.length;
}
console.log (
forCheck.map(scobs => check(scobs))
);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment