TL:DR — окончательный код
function balancedBrackets(string, openArr = []) {
let stack = openArr
let arr = []
if (typeof string === 'string') {
arr = string.split('')
} else {
arr = string
}
if (stack.length === 0 && arr.length === 0) {
return true
}
const char = arr.shift()
if (char === ')' || char === ']' || char === '}') {
if (stack.length === 0) {
return false
} else {
stack.push(char)
stack = check(stack)
}
}
if (char === '(' || char === '[' || char === '{') {
if (arr.length === 0) {
return false
} else {
stack.push(char)
stack = check(stack)
}
}
if (stack === false) {
return false
}
if (stack.length > 0 && arr.length === 0) {
return false
} else if (balancedBrackets(arr, stack)) {
return true
} else {
return false
}
}
const check = (array) => {
const size = array.length
if (size > 1) {
const prev = array[size-2]
const last = array[size-1]
if ((prev === '(' && last === ')') ||
(prev === '[' && last === ']') ||
(prev === '{' && last === '}')) {
return popTwo(array)
} else if (last === ')' || last === ']' || last === '}') {
return false
}
}
return array
}
const popTwo = (array) => {
array.pop()
array.pop()
return array
}
Это вернет
balancedBrackets('(hello)[world]')
// return true
balancedBrackets('{}')
// true
balancedBrackets('[({}{}{})([])]')
// true
balancedBrackets('(hello')
// false
balancedBrackets('([)]')
// false
balancedBrackets(')(')
// false
Теперь шаг за шагом, как это работает
Я учусь в Microverse, и мы получили задание по программированию, это довольно стандартное задание по программированию.
Задача кодирования, как определено Microverse,
Существует 3 вида скобок: [] {} (). Учитывая строку символов, проверьте, все ли скобки в строке сбалансированы. Строка сбалансирована, если все начальные и конечные скобки расположены в правильном порядке и соответствуют друг другу.
Вот несколько сбалансированных струн:
- {}
- (Привет, мир]
- [({}{}{})([])]
Вот несколько несбалансированных:
- (привет — без окончания)
- ([)] — [ неправильно заключено в ().
- )( — Есть окончание) без ( перед ним.
Возвращает true, если линия сбалансирована, и false в противном случае.
Я видел, как эта проблема решалась с помощью for loop и стеков, но я подумал, а как насчет использования рекурсии? Потому что рекурсия странная.
Трудно отлаживать и требует другого способа думать об этом. По сути, рекурсия = начало.
Авария
С рекурсией вам нужно учитывать, что ваша функция может работать вечно, то есть вы должны определить логику, которая будет сходиться и завершать цикл.
В этом случае я начал с определения более простого случая, когда вместо 3 разных скобок у нас есть только 1, который будет ( ), и отсюда я определил, как должна работать логика для нескольких простых случаев, и проанализировал, как можно анализировать каждый символ.
### Case 1 ()( ### Case 2 ()() ### Case 3 (()) ### Case 4 )()
Теперь я думаю, что нужно идти посимвольно, и первое, что мне нужно предположить, это то, что данная строка не имеет сбалансированных скобок. Причина в том, что если строка не сбалансирована, мы можем остановить выполнение, как только найдем условие.
Имея это в виду, мы можем определить, какие случаи приведут к определению, если у нас нет сбалансированных скобок, и отслеживать все открытые скобки (нам нужно будет использовать массив, где, если мы находим открытую скобку, мы помещаем ее в массив, и если мы найдем соответствующую закрывающую скобку, мы можем удалить последнюю добавленную открытую скобку.
Ищите условия, при которых код должен «сломаться»
Цель состоит в том, чтобы определить, какие случаи позволяют вам остановиться, как только будет найдено что-то, что не даст сбалансированных скобок. Например:
If: - the first bracket we find is ) - the last bracket is ( - there's an instance where brackets are not closed )( then: it is not a balanced bracket string
Когда это определено, нам понадобится способ следить за тем, какие скобки мы нашли, пока проверяем строку. Для этого мы можем создать массив, который будет действовать как стек. Этот стек будет иметь следующие свойства
Stack = [] If the first element is ) it means that the brackets are not balanced If the last element, that is bracket, is ( it means that brackets are not balanced either If brackets are back to back, )( the string is not balanced
Ищите условия, при которых вы можете окончательно сказать, что он сбалансирован.
Теперь мы знаем, когда струна определенно не сбалансирована. Найдем, какие случаи сбалансированы:
If the string has been checked and there was no 'break' then it's balanced
Это было легко.
Создание кода
Я использую JavaScript, но логика работает и на других языках программирования.
Сначала мы определяем функцию с 2 аргументами и 3 переменными.
function balancedBrackets(string, openArr = []) {
let stack = openArr
let arr = []
if (typeof string === 'string') {
arr = string.split('')
} else {
arr = string
}
const char = arr.shift()
balancedBrackets(arr, stack)
}
Объяснение переменных
стек: он будет передан «вниз» при следующем выполнении функции balanceBrackets.
arr: возьмет строку и «расширит» символы в массиве, чтобы с ним было проще работать.
char: возьмет первый символ строки для ее анализа.
Определение «точек останова»
Теперь мы переходим к определению того, что происходит, когда анализируемый char является скобкой.
function balancedBrackets(string, openArr = []) {
let stack = openArr
let arr = []
if (stack.length === 0 && arr.length === 0) {
return true
}
const char = arr.shift()
if (char === ')') {
if (stack.length === 0) {
return false
}
}
if (char === '(') {
if (arr.length === 0) {
return false
}
}
balancedBrackets(arr, stack)
Теперь вы можете заметить, что это работает, чтобы определить, можем ли мы сказать прямо в начале или в конце строки, сбалансирована ли строка, но у него нет способа определить, что произойдет дальше.
Для этого мы добавим способ запихнуть найденную скобку в стек, если мы еще не можем определить, сбалансирована ли строка.
function balancedBrackets(string, openArr = []) {
let stack = openArr
let arr = []
if (typeof string === 'string') {
arr = string.split('')
} else {
arr = string
}
if (stack.length === 0 && arr.length === 0) {
return true
}
const char = arr.shift()
if (char === ')') {
if (stack.length === 0) {
return false
} else {
stack.push(char)
stack = check(stack)
}
}
if (char === '(') {
if (arr.length === 0) {
return false
} else {
stack.push(char)
stack = check(stack)
}
}
if (stack === false) {
return false
}
balancedBrackets(arr, stack)
}
const check = (array) => {
const size = array.length
if (size > 1) {
const prev = array[size-2]
const last = array[size-1]
if (prev === '(' && last === ')') {
return popTwo(array)
} else if (last === ')') {
return false
}
}
return array
}
const popTwo = (array) => {
array.pop()
array.pop()
return array
}j
Функции «check» и «popTwo» — это утилиты, созданные вне функции balancedBrackets.
Задача check состоит в том, чтобы проверить, является ли стек «действительным» или мы должны объявить строку несбалансированной. Поэтому мы также добавили способ проверки того, возвращает ли функция check false.
check также удалит символы из стека, если они совпадают. Для этого мы определили popTwo, который удалит 2 элемента из стека.
Когда и где должна выполняться рекуррентная функция?
Раньше мы вызывали функцию без каких-либо ограничений, но это не сработает, поэтому мы определяем условия, которые будут определять, когда функция должна выполняться рекурсивно.
function balancedBrackets(string, openArr = []) {
let stack = openArr
let arr = []
if (typeof string === 'string') {
arr = string.split('')
} else {
arr = string
}
if (stack.length === 0 && arr.length === 0) {
return true
}
const char = arr.shift()
if (char === ')') {
if (stack.length === 0) {
return false
} else {
stack.push(char)
stack = check(stack)
}
}
if (char === '(') {
if (arr.length === 0) {
return false
} else {
stack.push(char)
stack = check(stack)
}
}
if (stack === false) {
return false
}
if (stack.length > 0 && arr.length === 0) {
return false
} else if (balancedBrackets(arr, stack)) {
return true
} else {
return false
}
}
Мы определяем ряд условий, которые приведут к определению того, является ли строка окончательно сбалансированной или нет. В начале оператора проверяется, не пуст ли стек и arr, содержащий строку, пуст, что означает, что строка не сбалансирована.
Если это не так, мы запускаем balancedBrackets, чтобы увидеть, возвращает ли он true или false, с версией строки, в которой был удален первый элемент. Если он возвращает true, то это означает, что все символы проанализированы и строка сбалансирована.
Если в какой-то момент balancedBrackets возвращает false, это означает, что строка не сбалансирована.
Хорошо, круто, а как насчет случая с 3-мя разными кронштейнами??
Нам нужны лишь небольшие дополнения. В основном, везде, где мы проверяем из скобок, мы добавляем случаи и для ВСЕХ скобок.
Это приводит нас к…
Окончательный код, в последний раз✨
function balancedBrackets(string, openArr = []) {
let stack = openArr
let arr = []
if (typeof string === 'string') {
arr = string.split('')
} else {
arr = string
}
if (stack.length === 0 && arr.length === 0) {
return true
}
const char = arr.shift()
if (char === ')' || char === ']' || char === '}') {
if (stack.length === 0) {
return false
} else {
stack.push(char)
stack = check(stack)
}
}
if (char === '(' || char === '[' || char === '{') {
if (arr.length === 0) {
return false
} else {
stack.push(char)
stack = check(stack)
}
}
if (stack === false) {
return false
}
if (stack.length > 0 && arr.length === 0) {
return false
} else if (balancedBrackets(arr, stack)) {
return true
} else {
return false
}
}
const check = (array) => {
const size = array.length
if (size > 1) {
const prev = array[size-2]
const last = array[size-1]
if ((prev === '(' && last === ')') ||
(prev === '[' && last === ']') ||
(prev === '{' && last === '}')) {
return popTwo(array)
} else if (last === ')' || last === ']' || last === '}') {
return false
}
}
return array
}
const popTwo = (array) => {
array.pop()
array.pop()
return array
}
