HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavascriptMinor

Checking for balanced brackets in JavaScript

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
javascriptcheckingbracketsbalancedfor

Problem

I'm wrote a simple function isBalanced which takes some code and returns true if the brackets in the code are balanced and false otherwise:

function isBalanced(code) {
    var length = code.length;
    var delimiter = '';
    var bracket = [];
    var matching = {
        ')': '(',
        ']': '[',
        '}': '{'
    };

    for (var i = 0; i < length; i++) {
        var char = code.charAt(i);

        switch (char) {
        case '"':
        case "'":
            if (delimiter)
                if (char === delimiter)
                    delimiter = '';
            else delimiter = char;
            break;
        case '/':
            var lookahead = code.charAt(++i);
            switch (lookahead) {
            case '/':
            case '*':
                delimiter = lookahead;
            }
            break;
        case '*':
            if (delimiter === '*' && code.charAt(++i) === '/') delimiter = '';
            break;
        case '\n':
            if (delimiter === '/') delimiter = '';
            break;
        case '\\':
            switch (delimiter) {
            case '"':
            case "'":
                i++;
            }
            break;
        case '(':
        case '[':
        case '{':
            if (!delimiter) bracket.push(char);
            break;
        case ')':
        case ']':
        case '}':
            if (!delimiter && bracket.length && matching[char] !== bracket.pop())
                return false;
        }
    }

    return bracket.length ? false : true;
}


The function must not operate on brackets inside strings and comments. I wanted to know if my current implementation will work correctly for all test cases. I also wanted to know whether brackets may be used in any other context beside strings and comments in a language like JavaScript (AFAIK this is not the case).

Solution

The function must not operate on brackets inside strings and comments.

If that's the case then why not just compare the number of opened vs closed symbols?

Example:

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;
};


Simple Testcases.

console.log( isBalanced( "var a = function(){return 'b';}" ) === true ); 
console.log( isBalanced( "var a = function(){return 'b';" ) === false ); 
console.log( isBalanced( "/*Comment*/var a = function(){ \n // coment again \n return 'b';" ) === false ); 
console.log( isBalanced( "var a = function(){return 'b';" ) === false );


Here's a demo:
http://jsfiddle.net/9esyk/
Update

Your code is optimal if performance is the main consideration, but the complexity is too high.
Here are a few tips.
1)

Split up your function into smaller methods to reduce the complexity. One way to do this would be to have functions to filter your string so that you only analyze the meaningful characters.
2)

Avoid using the keyword char since it's a java reserved keyword.
Final Result:

var removeComments = function(str){
    var re_comment = /(\/[*][^*]*[*]\/)|(\/\/[^\n]*)/gm;
    return (""+str).replace( re_comment, "" );
};
var getOnlyBrackets = function(str){
    var re = /[^()\[\]{}]/g;
    return (""+str).replace(re, "");
};
var areBracketsInOrder = function(str){
    str = ""+str;
    var bracket = {
            "]": "[",
            "}": "{",
            ")": "("
        },
        openBrackets = [], 
        isClean = true,
        i = 0,
        len = str.length;
        
    for(; isClean && i<len; i++ ){
        if( bracket[ str[ i ] ] ){
            isClean = ( openBrackets.pop() === bracket[ str[ i ] ] );
        }else{
            openBrackets.push( str[i] );
        }
    }
    return isClean && !openBrackets.length;
};
var isBalanced = function(str){
    str = removeComments(str);
    str = getOnlyBrackets(str);
    return areBracketsInOrder(str);
};


Testcases

test("test isBalanced for good values", function(){
    var func = isBalanced;
    ok(func( "" ));
    ok(func( "(function(){return [new Bears()]}());" ));
    ok(func( "var a = function(){return 'b';}" ));
    ok(func( "/*Comment: a = [} is bad */var a = function(){return 'b';}" ));
    ok(func( "/*[[[ */ function(){return {b:(function(x){ return x+1; })('c')}} /*_)(([}*/" ));
    ok(func( "//Complex object;\n a = [{a:1,b:2,c:[ new Car( 1, 'black' ) ]}]" ));
});
test("test isBalanced for bad values", function(){
    var func = isBalanced;
    ok(!func( "{" ));
    ok(!func( "{]" ));
    ok(!func( "{}(" ));
    ok(!func( "({)()()[][][}]" ));
    ok(!func( "[//]" ));
    ok(!func( "[/*]*/" ));
    ok(!func( "(function(){return [new Bears()}())];" ));
    ok(!func( "var a = [function(){return 'b';]}" ));
    ok(!func( "/*Comment: a = [} is bad */var a = function({)return 'b';}" ));
    ok(!func( "/*[[[ */ function(){return {b:(function(x){ return x+1; })'c')}} /*_)(([}*/" ));
    ok(!func( "//Complex object;\n a = [{a:1,b:2,c:[ new Car( 1, 'black' ) ]]" ));
});


Demo: http://jsfiddle.net/9esyk/3/

Code Snippets

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;
};
console.log( isBalanced( "var a = function(){return 'b';}" ) === true ); 
console.log( isBalanced( "var a = function(){return 'b';" ) === false ); 
console.log( isBalanced( "/*Comment*/var a = function(){ \n // coment again \n return 'b';" ) === false ); 
console.log( isBalanced( "var a = function(){return 'b';" ) === false );
var removeComments = function(str){
    var re_comment = /(\/[*][^*]*[*]\/)|(\/\/[^\n]*)/gm;
    return (""+str).replace( re_comment, "" );
};
var getOnlyBrackets = function(str){
    var re = /[^()\[\]{}]/g;
    return (""+str).replace(re, "");
};
var areBracketsInOrder = function(str){
    str = ""+str;
    var bracket = {
            "]": "[",
            "}": "{",
            ")": "("
        },
        openBrackets = [], 
        isClean = true,
        i = 0,
        len = str.length;
        
    for(; isClean && i<len; i++ ){
        if( bracket[ str[ i ] ] ){
            isClean = ( openBrackets.pop() === bracket[ str[ i ] ] );
        }else{
            openBrackets.push( str[i] );
        }
    }
    return isClean && !openBrackets.length;
};
var isBalanced = function(str){
    str = removeComments(str);
    str = getOnlyBrackets(str);
    return areBracketsInOrder(str);
};
test("test isBalanced for good values", function(){
    var func = isBalanced;
    ok(func( "" ));
    ok(func( "(function(){return [new Bears()]}());" ));
    ok(func( "var a = function(){return 'b';}" ));
    ok(func( "/*Comment: a = [} is bad */var a = function(){return 'b';}" ));
    ok(func( "/*[[[ */ function(){return {b:(function(x){ return x+1; })('c')}} /*_)(([}*/" ));
    ok(func( "//Complex object;\n a = [{a:1,b:2,c:[ new Car( 1, 'black' ) ]}]" ));
});
test("test isBalanced for bad values", function(){
    var func = isBalanced;
    ok(!func( "{" ));
    ok(!func( "{]" ));
    ok(!func( "{}(" ));
    ok(!func( "({)()()[][][}]" ));
    ok(!func( "[//]" ));
    ok(!func( "[/*]*/" ));
    ok(!func( "(function(){return [new Bears()}())];" ));
    ok(!func( "var a = [function(){return 'b';]}" ));
    ok(!func( "/*Comment: a = [} is bad */var a = function({)return 'b';}" ));
    ok(!func( "/*[[[ */ function(){return {b:(function(x){ return x+1; })'c')}} /*_)(([}*/" ));
    ok(!func( "//Complex object;\n a = [{a:1,b:2,c:[ new Car( 1, 'black' ) ]]" ));
});

Context

StackExchange Code Review Q#14532, answer score: 8

Revisions (0)

No revisions yet.