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

    }
}

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