Hackerrank CTCI "Stacks: Balanced Brackets" Javascript Solution

Question

Here is the original problem, and below is my solution. I wonder what can be improved? Or is there a fundamentally better algorithm out there? Thank you! My intuition is telling me that it can be more concise and efficient than this.

Input Format

The first line contains a single integer, , denoting the number of strings. Each line of the subsequent lines consists of a single string, , denoting a sequence of brackets.

Output Format

For each string, print whether or not the string of brackets is balanced on a new line. If the brackets are balanced, print YES; otherwise, print NO.

function main() {
 var t = parseInt(readLine());
 var i, isBalanced, stack, exp, len
 for (var a0 = 0; a0 < t; a0++) {
 exp = readLine().split('');
 stack = [];
 isBalanced = true;
 i = -1;
 len = exp.length;
 while (++i < len) {
 switch (exp[i]) {
 case "{":
 case "[":
 case "(":
 stack.push(exp[i])
 break;
 case "}":
 if (stack.pop() !== "{") {
 isBalanced = false
 }
 break;
 case "]":
 if (stack.pop() !== "[") {
 isBalanced = false
 }
 break;
 case ")":
 if (stack.pop() !== "(") {
 isBalanced = false
 }
 break;
 default:
 }
 if (isBalanced === false) {
 console.log("NO")
 break;
 }
 }
 if (isBalanced === true) {
 if (stack.length > 0) {
 if (stack[0] === "{" || stack[0] === "[" || stack[0] === "(") {
 console.log("NO")
 }
 } else {
 console.log("YES");
 }
 }
 }
}

• Mike Brant: I had answered a similar post in the past, which you may want to review for additional thoughts around algorithmic approach codereview.stackexchange.com/questions/147259/… I myself was surprised that an alternate implementation using regex could be demonstrated to perform better in many circumstances (though this is a classic "stack" problem).
• Dream_Cap: This answer helped me alot with understanding the problem. But I was wondering why do you have the isBalanced === true if statement checking the opening brackets? What is its purpose. Is it just for some odd test cases? I was struggling really hard on this problem for days.

Answer 1

Simplify matching parentheses

These case statements are very similar, and take a couple of lines to write:

case "}":
 if (stack.pop() !== "{") {
 isBalanced = false
 }
 break;
case "]":
 if (stack.pop() !== "[") {
 isBalanced = false
 }
 break;
case ")":
 if (stack.pop() !== "(") {
 isBalanced = false
 }
 break;

You could simplify by reworking the case statements that handle the opening parentheses:

case "{":
 stack.push("}");
 break;
case "[":
 stack.push("]");
 break;
case "(":
 stack.push(")");
 break;

And then you could replace the handling of the closers with the simpler:

case "}":
case "]":
case ")":
 if (stack.pop() !== exp[i]) {
 isBalanced = false
 }
 break;

Avoid flag variables when possible

Instead of setting isBalanced = false and the multiple checks, it would be simpler in such cases to immediately print the result and break, for example:

next:
for (var a0 = 0; a0 < t; a0++) {
 exp = readLine().split('');
 stack = [];
 i = -1;
 len = exp.length;
 while (++i < len) {
 switch (exp[i]) {
 case "{":
 stack.push("}");
 break;
 case "[":
 stack.push("]");
 break;
 case "(":
 stack.push(")");
 break;
 case "}":
 case "]":
 case ")":
 if (stack.pop() !== exp[i]) {
 console.log("NO");
 continue next;
 }
 break;
 }
 }
 console.log(stack.length == 0 ? "YES" : "NO");

Naming

What is exp? It's not very obvious, but actually it's characters. How about calling it chars?

Answer 2

I took janos's answer and tried to improve on it, using a dictionary instead to look up the matching brackets, so we don't need all the switch cases anymore.

function main() {
 var t = parseInt(readLine());
 for(var a0 = 0; a0 < t; a0++){
 var expression = readLine();
 console.log(isBalanced(expression) ? 'YES' : 'NO')
 }
}
function isBalanced(expression) {
 chars = expression.split('');
 var stack = [];
 for (var i = 0; i < chars.length; i++) {
 var currentBracket = chars[i];
 if(currentBracket in BRACKETS_DICT) {
 // opening bracket
 // push closing bracket on stack
 stack.push(BRACKETS_DICT[currentBracket]);
 } else {
 // closing bracket
 // check if it matches the last on the stack
 if(stack.pop() !== currentBracket) {
 return false;
 }
 }
 }
 return stack.length === 0;
}
var BRACKETS_DICT = {
 '(': ')',
 '[': ']',
 '{': '}'
}