3
\$\begingroup\$

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

    }
}
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – Mike Brant Jun 20 '17 at 17:33
  • \$\begingroup\$ 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. \$\endgroup\$ – Dream_Cap Dec 11 '17 at 4:40
2
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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