# Hackerrank CTCI "Stacks: Balanced Brackets" Javascript Solution

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

}
}

• 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). Jun 20, 2017 at 17:33
• 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. Dec 11, 2017 at 4:40

## 2 Answers

### 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?

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 = {
'(': ')',
'[': ']',
'{': '}'
}