Как да проверите дали низ от ({[]}) е балансиран в JavaScript.
В този блог ще разгледам как да проверя дали низ от смес от { [ ( има съвпадащ затварящ)]}.
Структурата на данните, която искам да използвам, е Стек,който ще бъде масив, но със специална функционалност за по-лесна работа.
Стекът е линейна структура от данни, която следва определен ред, в който се изпълняват операциите. Редът може да бъде LIFO (последен влязъл, първи излязъл) или FILO (първи влязъл, последен излязъл).
Най-добрият начин, по който мога да се сетя за Stack, е ако си представите купчина чинии. Ако ги натрупате или ги подредите, ще започнете с една чиния и след това ще поставите друга върху първата и така нататък, докато получите купчина чинии. Последната чиния е горната част на купчината и ще бъде първата, която ще бъде премахната, ако имате нужда от чиния. Първата чиния, която поставите в стека, ще бъде последната чиния, която ще бъде премахната или използвана.
Със стек ще мога да избутвам (добавям) нови елементи в края на масива (в изгледа на стека) горната част от стека. pop (премахване) ще премахне последния елемент от масива, елемента в горната част, като по този начин следва операцията LIFO (последен влязъл, първи излязъл). Освен това ще внедря операцията peek, за да получа последния елемент (отгоре) от стека.
Време за кодиране
Създадох функция isBalanced(string), която приема аргумент, който може да бъде произволна последователност от отварящи и затварящи скоби ((({[]}))) и връща или ДА или НЕ, ако е балансиран (съвпадение на отваряне и затваряне).
В ред 3 ето как създадох стек, който всъщност е масив. Можете да го кръстите както искате, просто реших да го кръстя стек за простота.
След това итерирам (редове 5–13) през низа, за да проверя дали елементите са лявата страна на скобите [({, ако е така, добавете ги (натиснете) към стека. Ако през тази итерация има нещо освен лявата страна на скоба (редове 8–11), проверете дали стекът не е празен и дали. горният елемент в стека (лявата страна) и текущият елемент в цикъла (дясната страна) са двойка.
За целта създадох 2 помощни функции,isPair, които проверяват дали ( ) {} [ ] са двойка и връщат true, ако са.
Втората помощна функция, peek, това можеше да бъде направено директно на ред 9, но го направих повече за визуализация на структура от данни на Stack, която трябва да има функция peek , които връщат горния елемент или последния елемент в масива.
За да продължите на ред 9, ако тази функция върне true, изскача (премахва) елемента от стека. В края на цикъла (итерации), ако стекът е празен, тогава низът (аргументът) е балансиран и връща ДА. В противен случай той все още има елементи в стека и не е балансиран, връщайки НЕ.
Можете да видите тази функция в действие и тестовия пакет в моето репо в GitHub.
