Как проверить баланс скобок?

Question

[Dmytro Bezvoshchuk]

Здравствуйте Тостер-сообщество!

Помогите пожалуйста с небольшим заданием...
Есть JS-код. Нужно написать JS-код, который определяет, соблюдается ли в нем баланс скобок (простых и фигурных).
Например:
js("function test(){ alert(); }") -> true
js("function test)({ alert(); }") -> false

Заранее прошу прощения, если вопрос уж слишком нубский, но я только учусь :)

Comments

[Евгений Ахметов]

Язык программирования без разницы ?

[Dmytro Bezvoshchuk]

Евгений Ахметов: JS

[copal]

Евгений Ахметов: парсите с двух сторон одновременно с помощью indexOf и lastIndexOf.
И если в одной итерации левая не открывающая или правая не закрывающая, то значит ошибка.

[Евгений Ахметов]

copal: Спасибо конечно, я то знаю :)

[Евгений Ахметов]

d1monster: Как уже написали, циклом проверяйте с помощью indexOf и lastIndexOf. В каждей итерации подставляя соответствующие смещения.

Answer 1

[Dmitriy Mozgovoy]

Где то так... https://jsfiddle.net/DigitalBrain/azj0u01d/

function js(text){
         var i,
                 l=text.length,
                 char,
                 last,
                 stack=[];

         for(i=0; i<l; i++){
             char=text[i];

             if(char=="{" || char=="("){
                 stack.push(char);
             }else if(char=="}" || char==")"){
                 if(stack.length>0){
                     last=stack[stack.length-1];
                     if ((char == '}' && last == "{") || (char == ')' && last == '(')) {
                         stack.pop();
                     }
                 }
             }
         }
         return stack.length==0;
     }
     console.info(js("function test(){ alert(); }")); // true
     console.info(js("function test)({ alert(); }")); //false

Слегка оптимизировал

function js(text){
         var i, l=text.length,  char,  last, stack=[];

         for(i=0; i<l; i++){
             char=text[i];
             if(char=="{" || char=="("){
                 stack.push(char);
                 last=char;
             }else if(char == '}' || char == ")"){
                 if(last){
                     if((char == '}' && last == "{") || (char == ')' && last == '('))
                     {
                         stack.pop();
                         last = stack.length > 0 ? stack[stack.length - 1] : undefined;
                     }
                 }else{
                     return false;
                 }
             }
         }
         return stack.length==0;
     }

Comments

[Dmytro Bezvoshchuk]

Огромное Вам спасибо!

[Stalker_RED]

расширил до произвольного набора скобок jsfiddle.net/zwmx3omr

[Stalker_RED]

кстати, заменив return false на return i, можно возвращать не просто true-false, а позицию первого ошибочного символа.

[Dmitriy Mozgovoy]

Stalker_RED: да, у меня та же мысль была, но воздержался и решил не усложнять=)
P.S в Вашем коде образовался смачный косяк в одном месте, подсказка console.info(js("function test(){ alert(){]; }")); //?

[Stalker_RED]

Digital Brain: ага, поторопился. в вашем коде тоже нашелся баг: "function test(){ alert(]); }"
подправил: jsfiddle.net/zwmx3omr/1

[Dmitriy Mozgovoy]

Stalker_RED: хех, баг репорт отклонен- в ТЗ автора только 2 типа скобок =))
Угу, кажется, подправили, осталось только оптимизировать типа last=stack.pop(); и вместо сравнения индексов, сравнить last!=br_opn[bcc] дабы не делать обход массива лишний раз, хотя это я конечно придираюсь. Все, будем гитхабить - код года=))

[Dmytro Bezvoshchuk]

Digital Brain, в Вашем коде есть тоже небольшой косяк:
console.info(js("function test(){ alert); }")); -> true :)

[Dmytro Bezvoshchuk]

Digital Brain, помогите еще пожалуйста розобраться с логикой происходящего...
В цикле for мы перебираем тестируемый код.
В каждой итерации char = text[i]
Далее если char == { или ( , тоесть условие true то мы добавляем этот символ в конец масива stack.
Но зачем мы делаем last = char ?
И если char == { или ( то else if не срабатывает и мы переходим сразу к
return stack.length==0;
Но ведь длина этого масива не ноль, в нем есть char == { или (

[Dmytro Bezvoshchuk]

Stalker_RED по Вашему решению еще хотел утчонить по устловию проверки br_opn.indexOf(char) != -1
Что значит "!= -1" ? Аналогично ли это выражение выражению ">=0" ?

Ребят, не поймите неправильно, просто хочу разобраться.

[Dmitriy Mozgovoy]

d1monster: а вот этот Баг засчитан=) Раз уже исправлял, то добавил и словарь скобок jsfiddle.net/DigitalBrain/swkdtphs

[Dmitriy Mozgovoy]

d1monster: это оптимизация производительности, чтоб запомнить последний символ в массиве, который нужный в условии обнаружения закрывающей скобки при сравнении. Можно было выкинуть last, но тогда, чтоб получить последнюю открытую скобу придется писать и не раз stack[stack.length - 1] и тем самым каждый раз раз обращаться к массиву и его длине, что медленнее, чем просто к готовой переменной, вообщем это кеш последней открытой скобы своего рода. При добавлении в конец массива запомнили что последняя в массиве и есть char, тогда нет нужды опять проверять какой же там последний элемент. А при удалении pop обновляем last=stack[stack.length - 1];
"И если char == { или ( то else if не срабатывает" да... не сработает и не должно ведь мы уже определили, что текущий символ принадлежит к открывающим скобкам, он не кот Шредингера и он не может принадлежать к открывающим и закрывающим скобам одновременно=). Дальше цикл продолжится, т.е будет следующая итерация, и проверка следующего символа.

[Dmitriy Mozgovoy]

d1monster: ну а в else if мы проверяем закрывающие скобы с оптимизацией : если нет открытой скобы last==false то проверять дальше нет смысла- ошибка уже обнаружена, иначе сверяем последнюю открытую скобу с типом закрывающей, если совпадает - текущие скобы закрылись - удаляем ее с stack, обновляем last, проверяем дальше. Иначе ошибка - несовпадение открывающей и закрывающей скобки - ошибка, дальше проверять незачем.

[Stalker_RED]

d1monster: indexOf() ищет позицию символа в строке или элемента в массиве. Если элемент не найден - возвращается -1.
Да, в принципе выражение (x != -1) равнозначно (x >= 0), но традиционно сравнивают с -1, т.к. это очень явный намек на то, что в этом месте проверяется наличие элемента в массиве, а не какое-то непонятное сравнение.

[Dmitriy Mozgovoy]

Stalker_RED: кстати, br_opn = '({[<' а с меньше- больше что будет то?=) console.info(7,js("fun}ction test(){ alert(x>0?1:0); }"));

[Stalker_RED]

Digital Brain: я их чисто для примера туда вставил.

[Dmytro Bezvoshchuk]

Digital Brain, последний момент... Что делает последняя строка return !last; ?

[Dmitriy Mozgovoy]

d1monster: =)) проверяет пустой ли массив (раньше там было stack.length==0, но так оптимальнее)- в last на протяжении всего алгоритма был последний символ в массиве, т.е если его там нет - то все скобы закрылись, иначе что то осталось и это ошибка.

[Dmitriy Mozgovoy]

d1monster: P.S подозреваю, что это задача с собеседования, либо задачи с тренинга для стажеров? Что то так долго и усердно неделю пытаетесь ее осознать "до винтика"... =)

[Dmytro Bezvoshchuk]

Digital Brain не совсем :) Вот уже год верстаю и уверенно себя в верстке чувствую, решил что пора двигаться дальше. Задача действительно тестовая, но от коллег. Пытаюсь её осознать до винтика всего лишь для своего развития.

Answer 2

[Евгений Ахметов]

Включите консоль браузера, если что-то не так с синтаксисом Вам покажет где ошибка.

Comments

[Dmytro Bezvoshchuk]

Евгений, извините за неточность, но нужно программное решение.
Исправил описание вопроса.