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

Question

[kiberlain]

есть строка var s = 'foo(bar[baz]){qux}'
Надо проверить что в ней правильно расставлены скобочки. С чего начать?

Comments

[Алексей Уколов]

Опишите для начала что в данном случае означает "правильно"

[Lynn «Кофеман»]

mech.math.msu.su/~shvetz/54/inf/perl-problems/chBa...

Answer 1

[SHVV]

Ололошки уже три ответа и ни одного правильного.

function isBalanced(str) {
    // пары открывающих-закрывающих скобок
    var br = "(){}[]";
    // стек открытых скобок
    var st = [];
    // бежим по всей строке
    for (var i = 0; i < str.length; ++i) {
        // текущий символ
        var ch = str[i];
        // ищем символ в скобках
        var ind = br.indexOf(ch);
        // если скобка найдена
        if (ind >= 0) {
            // проверяем, какая это скобка
            if (ind & 1) {
                // если закрывающая скобка, проверяем стек
                // стек пуст - плохо
                if (!st.length) return false;
                // извлекаем последнюю открытую скобку из стека
                var last_br = st.pop();
                // если она не соответствует закрывающей скобке - тоже плохо
                if (last_br != br[ind - 1]) return false;
            } else { 
                // открывающую скобку просто пихаем в стек
                st.push(ch);
            }
        }
    }
    // если после обхода всей строки стек пуст - всё ок
    return !st.length;
}

Проверять тут.

Comments

[mrDii]

а что за проверка if (ind & 1) ?

[SHVV]

ind это индекс скобки в массиве var br = "(){}[]";
Они распложены так, что четные скобки открывающие, нечётные закрывающие (индекс начинается с нуля).
if (ind & 1) проверяет младший бит на 1 с помощью бинарного "и". Если он 1, то это индекс нечётный, соответствует закрывающей скобке.

Answer 2

[IceJOKER]

самая первая мысль - подсчитать кол. открытых скобок и закрытых - если равны, значит все окей(но тут есть загвоздка с расположением скобок)

if(s.split("(").length == s.split(")").length) alert('ok'); else alert('not ok')

Answer 3

[Александр]

(s.split('(') !== s.split(')')) || (s.split('[') !== s.split(']')) || (s.split('{') !== s.split('}'))

Это если подвхождения не учитывать, с подвхождениями - в рекурсии проверяете каждый элемент массива s.split

Answer 4

[Сергей Наломенко]

Например, с помощью вот такой функции isBalanced():

var haveSameLength = function(str, a, b){
    return (str.match(a) || [] ).length === (str.match(b) || [] ).length;
};
var isBalanced = function(str){
    var arr = [ 
        [ /\(/gm, /\)/gm ], [ /\{/gm, /\}/gm ], [ /\[/gm, /\]/gm ] 
    ], i = arr.length, isClean = true;

    while( i-- && isClean ){
        isClean = haveSameLength( str, arr[i][0], arr[i][1] );
    }
    return isClean;
};

Более полный разбор полётов тут