patternjavascriptMinor
Checking for balanced brackets in JavaScript
Viewed 0 times
javascriptcheckingbracketsbalancedfor
Problem
I'm wrote a simple function
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).
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.