Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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).

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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/

share|improve this answer
    
When you check for balanced brackets you must ensure that an opening bracket comes before a closing bracket. Your code doesn't take that into account and fails if say a function is declared with a closing brace before an opening brace (which is invalid) but your code passes it. –  Aadit M Shah Sep 6 '12 at 14:32
    
@AaditMShah Updated my answer. Thanks for the response. –  Larry Battle Sep 6 '12 at 21:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.