Check whether string of braces, brackets, and parentheses is balanced

Question

The Task

is taken from codewars:

Write a function that takes a string of braces, and determines if the order of the braces is valid. It should return true if the string is valid, and false if it's invalid.

All input strings will be nonempty, and will only consist of parentheses, brackets and curly braces: ()[]{}.

What is considered Valid? A string of braces is considered valid if all braces are matched with the correct brace.

Examples

• (){}[] => True
• ([{}]) => True
• (} => False
• [(]) => False
• [({})](] => False

My solution

const areBracesBalanced = brc => {
  const brace = Object.freeze({
    "(": [],
    "[": [],
    "{": [],
  });

  const removeBrace = b => brace[b].splice(-1, 1);
  const getLastBraceIndex = b => brace[b][brace[b].length - 1]
  const braceExists = b => !brace[b].length;
  const isBraceBeforeClosed = (before, current) => braceExists(before) || getLastBraceIndex(before) < getLastBraceIndex(current);

  const braceIsBalanced = (b, i) => {
    switch (b) {
      case "(":
      case "[":
      case "{":
        return brace[b].push(i);
      case ")":
        return isBraceBeforeClosed("[", "(") &&
               isBraceBeforeClosed("{", "(") &&
               removeBrace("(");
      case "]":
        return isBraceBeforeClosed("(", "[") &&
               isBraceBeforeClosed("{", "[") &&
               removeBrace("[");
      case "}":
        return isBraceBeforeClosed("(", "{") &&
               isBraceBeforeClosed("[", "{") &&
               removeBrace("{");
      default:
        // be a good code...
    }
  };

  return[...brc]
    .every(braceIsBalanced) && !Object.values(brace).flat().length;
}

Answer 1

Your solution is complicated due to the use of three separate stacks:

• For each closing character, you have to cross-validate the two other types of delimiters. (If you had to handle a fourth type of matching characters, such as < and >, it would be even messier.)
• At the end, you need to write !Object.values(brace).flat().length to verify that all of the stacks have been cleared.

I also think that the use of Object.freeze() is overkill.

Your removeBrace() helper can use Array.prototype.pop() instead.

Suggested solution

Keep all of the state in one combined stack.

const areBracesBalanced = brs => {
  let expectCloseStack = [];
  return [...brs].every(b => {
    switch (b) {
      case "(": return expectCloseStack.push(")");
      case "[": return expectCloseStack.push("]");
      case "{": return expectCloseStack.push("}");

      case ")":
      case "]":
      case "}":
        return expectCloseStack.pop() === b;
    }
  }) && !expectCloseStack.length;
};

console.log(areBracesBalanced("[({})](]"));

Answer 2

I'm not very good at Javascript, but I do know how to make an algorithm.

In the code below I use the fact that correct {} or [] or () will always touch and can be removed. Just taken these away until there aren't any left and if you've got an empty string it was balanced, if it is not empty then clearly it must be unbalanced.

function isBalanced(input)
{
    while (input.length > 0) {
    var output = input.replace("{}", "").replace("[]", "").replace("()", "");
        if (input == output) return false;
        input = output;
    }
    return true;
}

function test(input)
{
  alert("'"+input+"' = "+(isBalanced(input) ? "Correct" : "Incorrect"));
}

test("(){}[]");
test("([{}])");
test("(}");
test("[(])");
test("[({})](]");
test("(){[}]");

Someone with a bit more knowledge of Javascript might be able to further optimize this code.

To make it slightly more efficient there's a version with a regular expression:

function isBalanced(input)
{
    while (input.length > 0) {
        var output = input.replace(/\(\)|\{\}|\[\]/, "");
        if (input == output) return false;
        input = output;
    }
    return true;
}

I think this short code is elegant, but here it is somewhat at the expense of clarity.

Here's why the above code is an improvement:

• The code is a lot shorter.
• The code is easier the read.
• There's a simple algorithm that is explained.

Yes, the code might be less efficient, and doesn't build on the code in the question, and for that I apologize.