Не секрет, что существуют определенные игрушечные задачи, которые чрезвычайно популярны во время собеседований, и BalancedParens, похоже, является одной из них. Итак, давайте потратим время на его рассмотрение.
Первое пояснение, которое необходимо сделать по этой проблеме, - это то, что на самом деле подразумевается под «круглыми скобками». Технически круглыми скобками являются только "(" и ")". При решении этой проблемы мы будем исходить из предположения, что мы проверяем сбалансированность скобок, квадратных скобок [] и фигурных скобок {}. В этом обсуждении, когда я упоминаю «круглые скобки», я буду иметь в виду все три, если я специально не выделю их.
Давайте поговорим коротко, прежде чем погрузиться в то, что на самом деле делает этот алгоритм. Этот алгоритм на самом деле является служебной функцией, которая проверяет, сбалансированы ли круглые скобки или нет. С точки зрения использования, он имеет больше общего с проверкой грамматики, чем с алгоритмом, который выполняет такие действия, как управление вводом (например, алгоритм сортировки).
В реальных условиях на входе, скорее всего, будет какой-то код, который мы хотим проверить, точно так же, как мы запускаем документ Word через проверку орфографии и грамматики. Алгоритм вернет истину, если круглые скобки во входных данных сбалансированы, и вернет ложь в противном случае. Опять же, если не указано иное, «круглыми скобками» я имею в виду «(‘, ‘)’, ‘[‘, ‘]’, ‘{‘ и ‘}’.
Наш алгоритм будет предполагать, что мы взяли наш код и преобразовали его в строку. В академических целях мы будем рассматривать в основном строки, содержащие исключительно разные типы круглых скобок. Мы встроим в алгоритм функциональность, которая пропускает в строке все, кроме открывающих или закрывающих скобок.
EXAMPLE OF WHAT COULD BE PASSED IN:
let bubbleSort = (arr) => {
if (!arr || !Array.isArray(arr)) {
return 'please enter in an array of numeric values';
}
let countSwitch;
//set a while loop
while (countSwitch !== 0) {
countSwitch = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i + 1] < arr[i]) {
//do a switch
var firstVal = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = firstVal;
countSwitch ++;
}
}
}
return arr;
};
let bubbleSortString = bubbleSort.toString();
balancedParens(bubbleSortString);
WE'RE GOING TO PRIMARILY TEST OUR ALGORITHM BY PRIMARILY BY PASSING IN STRINGS COMPRISED ENTIRELY OF PARENTHESES, INCLUDING:
'(){}[]'
'()()[]{[]}[({})]'
'((((()))))'
'()[]{'
'(()))'
'((((('
Вероятно, вы видите, что некоторые из этих строк проходят, а другие нет. Есть несколько способов создать алгоритм, который вернет правильный ответ для приведенных выше строк. Но многие перестанут работать, когда мы найдем интересный вариант использования:
'()[({(){[}]})]'
В этом нет ничего плохого? Взгляни еще раз
0 1 2 3 4 5 6 7 8 9 10 11 12 13
'( ) [ ( { ( ) { [ } ] } ) ]'
^
Проблема здесь в том, что мы пытаемся закрыть внешние скобки до того, как закроем внутренние скобки. В частности, мы открыли фигурную скобку в индексе 7, а затем квадратную скобку в индексе 8. Затем мы пытаемся закрыть фигурную скобку в индексе 9, прежде чем закрывать нашу квадратную скобку, что мы пытаемся сделать в индексе 10.
И вот здесь в центре внимания находится решение. Чтобы правильно оценить круглые скобки в этой строке, всякий раз, когда мы нажимаем закрывающие круглые скобки любого типа, нам нужно спрашивать: «Сейчас подходящее время, чтобы закрыть эти круглые скобки?». И единственный способ решить это - отслеживать то, что открыто в данный момент, и порядок, в котором они были открыты.
Звучит много, но решение на самом деле довольно простое. Мы собираемся использовать структуру данных, называемую стеком.
Для непосвященных подумайте о матрешках (спасибо World Market за то, что они доступны для продажи)!
Как многие из нас знают, матрешки можно разобрать и собрать вместе, при этом куклы меньшего размера «вложены» в большую. Если бы я разложил части вокруг стола, это было бы достаточно легко.
Однако что, если я не смогу увидеть детали, но мне пришлось бы рассказать вам, как собрать куклу обратно? Я мог бы сказать «соедините вместе самую большую верхнюю часть и самую большую нижнюю часть», «соедините самую маленькую верхнюю часть и самую маленькую нижнюю часть» и т. Д., Но это не сработает. Почему? Потому что для правильного размещения кукол их части необходимо собрать по порядку. В частности, части должны были быть собраны вместе в обратном порядке, в каком бы порядке они не были разобраны. И здесь на помощь приходит наш стек.
Наш стек предоставляет нам «дорожную карту», которая сообщает нам, что мы до сих пор разбирали, чтобы добраться до самого сложного места. Таким образом, мы знаем порядок, в котором нужно собрать детали вместе.
Наш стек будет выглядеть так:
… И может быть абстрагирован следующим образом: [‘(‘, ‘{‘, ‘[‘]
У кукол «сбалансированная» струна будет выглядеть так:
И это можно было бы абстрагировать так:
‘({[]})’
Как только мы дойдем до места, где больше всего гнезд, первое, что нам нужно будет сделать, чтобы собрать куклу, - это посмотреть, совпадает ли деталь.
Если это так, мы вытаскиваем его из нашего стека, оставляя оставшиеся две наши части:
Если части уравновешены, мы получим красивую матрешку. В противном случае мы не сможем собрать куклу, по крайней мере, полностью. Как упоминалось ранее, этот алгоритм работает особенно хорошо, потому что он решает досадную проблему, когда порядок закрытия круглых скобок отключен, даже если есть все нужные части (как показано на куклах ниже):
Мы знаем, что не сможем собрать куклу в таком порядке. Синяя нижняя часть не «вписывается» в красную верхнюю и не может быть «вложена». В контексте нашей проблемы наш пример этого может выглядеть так:
‘([{]})’
Для простоты я буду использовать массив и методы .push () и .pop () для имитации поведения стека.
Давайте посмотрим на код решения и рассмотрим его:
balancedParens = (string) => {
let storage = [];
let openings = ['[', '{', '('];
let closings = [']', '}', ')'];
let opposites = {
')': '(',
']': '[',
'}': '{'
};
for (let char of string) {
if (openings.includes(char)) {
storage.push(char);
} else if (closings.includes(char)) {
let opposite = opposites[char];
let lastIndex = storage[storage.length - 1];
if (opposite !== lastIndex) {
return false;
} else {
let popped = storage.pop();
}
} else {
continue;
}
}
if (storage.length > 0) {
return false;
}
return true;
};
storage - это место, где мы собирались хранить элементы (т.е. открывающие скобки), которые мы помещаем в наш стек.
Теперь перейдем к циклу for. Для тех, кто не знаком с ES6, цикл «for… of» позволит нам перебирать символы в строке без необходимости каким-либо образом манипулировать строкой.
Для каждого символа, который мы перебираем в строке, есть три возможности:
ВОЗМОЖНОСТЬ ПЕРВАЯ: это открывающая скобка, квадратная или фигурная скобка (например, «(‘, [‘или‘ {‘).
ВОЗМОЖНОСТЬ ВТОРАЯ: это закрывающие круглые скобки, квадратные или фигурные скобки (т.е. ‘)’, ‘]’, ‘}’).
ВОЗМОЖНОСТЬ ТРЕТЬЯ: Это какой-то другой персонаж.
balancedParens = (string) => {
let storage = [];
let openings = ['[', '{', '('];
let closings = [']', '}', ')'];
let opposites = {
')': '(',
']': '[',
'}': '{'
};
for (let char of string) {
if (openings.includes(char)) { //Possibility One
storage.push(char);
} else if (closings.includes(char)) { //Possibility Two
let opposite = opposites[char];
let lastIndex = storage[storage.length - 1];
if (opposite !== lastIndex) {
return false;
} else {
let popped = storage.pop();
}
} else { //Possibility Three
continue;
}
}
if (storage.length > 0) {
return false;
}
return true;
};
Работать с третьей возможностью легко - нас не интересуют другие символы в строке, поэтому мы просто «пропускаем» эту итерацию, используя ключевое слово continue, и переходим к следующему символу в строке.
Когда мы нажимаем '(', '[' или '{', (первая возможность), мы добавляем еще один шаг к нашей «дорожной карте», что означает, что мы должны прикрепить этот шаг к концу нашего массива как последний ( или самый последний шаг). Мы используем метод .push () для загрузки в наш стек.
Магия этого алгоритма проявляется в блоке else if, который имеет дело со второй возможностью. Когда мы нажимаем ‘)‘, ‘]‘ или ‘}‘, мы знаем, что собираем все вместе, или, по крайней мере, пытаемся это сделать. У нас есть шаги в нашей «дорожной карте», хранящиеся в нашем стеке, поэтому все, что нам нужно сделать, это проверить, соответствуют ли закрывающие круглые скобки самым последним открывающим скобкам. Другими словами, если мы перебираем «)», а самый последний (т.е. последний) элемент в стеке - это «(», тогда все готово. Они совпадают, и мы можем очистить этот «шаг». стек (который мы сделаем с помощью собственного метода .pop ().
Фактически, в этом алгоритме есть два момента, когда мы определяем, являются ли круглые скобки несбалансированными. Один находится на данном этапе. Если мы перебираем, например, ']', а последним элементом в стеке будет '(', тогда мы автоматически узнаем, что круглые скобки не сбалансированы и могут вернуть 'false'. В идеале, если все сбалансировано, мы придем через соответствующие закрывающие скобки в обратном порядке, в котором мы встречались с открывающими скобками.
Когда круглые скобки сбалансированы, в нашем стеке не должно быть ничего - они все должны были быть очищены к концу цикла. Наш массив storage должен иметь нулевую длину.
Что, конечно, поднимает вопрос о ситуации, когда он не может быть равен нулю после завершения цикла. Я предлагаю пример ниже:
'(((([{}])'
Мы не столкнемся с какими-либо проблемами при удалении данных с конца стека, поскольку они будут очищены в правильном порядке, но круглые скобки все равно будут неуравновешенными, потому что у нас было больше открывающих скобок, чем закрывающих. В результате, как только цикл завершится, наш стек по-прежнему будет выглядеть так:
[ '(', '(', '(' ]
Итак, у нас есть второй тест в нашем алгоритме после завершения цикла, который просто проверяет длину массива хранения. Если что-нибудь (читай: лишние открытые круглые скобки) останется внутри, мы будем знать, что круглые скобки не сбалансированы и могут вернуть false.
И это все!
