How to check for valid braces in javascript, programming problem?

Question

have been struggling for the last couple of days with the following problem 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

So I'm really stuck with the code for this one, and this is what I have up to this point:

function validBraces(braces){
    let opening = [ '(', '[', '{']
    let closing = [ ')', ']', '}']
    let count = 0
    const left = []
    const right = []

    // I generate left and right arrays, left w/the opening braces from the input, right w/ the closing
    for (let i = 0; i < braces.length; i++) {
        if (opening.includes(braces[i])) {
            left.push(braces[i])
        } else if (closing.includes(braces[i])) {
            right.push(braces[i])
        }
    }
    if (braces.length % 2 !== 0) {
        return false
    }
    // I know there's no point in doing this but at one point I thought I was finishing the program and thought I would 'optimize it' to exit early, probably this is dumb haha.
    if (left.length !== right.length) {
        return false
    }
    // The juicy (not juicy) part where I check if the braces make sense
    for (let i = 0; i < left.length; i++) {
    // If the list are made up of braces like  ()[]{} add one to counter
        if (opening.indexOf(left[i]) === closing.indexOf(right[i])) {
            count += 1
        } else // If left and right are mirrored add one to the counter
            if (opening.indexOf(left[i]) === closing.indexOf(right.reverse()[i])) {
                count += 1
            }
}
    //If the counter makes sense return true
    if (count === braces.length / 2) {
        return true
    } else { return false}
}


console.log(validBraces( "()" )) //true
console.log(validBraces("([])")) //true
console.log(validBraces( "[(])" )) //false
console.log(validBraces( "[(})" )) //false
console.log(validBraces( "[([[]])]" )) //true

Some comments: I know I'm still not checking for this example ([])() but I thought of breaking this up into two smaller checks in some way.

Thank you if you read up to this point. I would appreciate guidance in some way, though I don't want the problem solved for me. I'm probably overcomplicating this in some way since its a 6kyu problem, if so a tip on how to approach it more cleverly would be very much appreciated.

Thank you in advance! :pray: :pray:

Answer 1

function validBraces(braces){
    let par =0;
    let bra =0;
    let cur =0;
    for(let i =0; i<braces.length; i++){
        if(braces[i]==="("){
            par++;
        }
        if(braces[i]===")"){
            par--;
        }
        if(braces[i]==="["){
            bra++;
        }
        if(braces[i]==="]"){
            bra--;
        }
        if(braces[i]==="{"){
            cur++;
        }
        if(braces[i]==="}"){
            cur--;
        }
    }

    if(par<0 || bra<0 || cur<0){
        return false;
    } 
    return true;
};

Answer 2

Here is a simplified solution:

let isMatchingBraces = function(str) {
    let stack = [];
    let symbol = {
        '(': ')',
        '[': ']',
        '{': '}'
    };
    for (let i = 0; i < str.length; i += 1) {
        // If character is an opening brace add it to a stack
        if (str[i] === '(' || str[i] === '{' || str[i] === '[') {
            stack.push(str[i]);
        }
        //  If that character is a closing brace, pop from the stack, which will also reduce the length of the stack each time a closing bracket is encountered.
        else {
            let last = stack.pop();
            //If the popped element from the stack, which is the last opening brace doesn’t match the corresponding closing brace in the symbol, then return false
            if (str[i] !== symbol[last]) {
                return false
            };
        }
    }
    // After checking all the brackets of the str, at the end, the stack is not 
    // empty then fail
    if (stack.length !== 0) {
        return false
    };
    return true;
}

Answer 3

Hell yeah!! I'm very happy to finally reach to the solution myself using some of the hints given to me here:

function validBraces(braces){
    let opening = [ '(', '[', '{']
    let closing = [ ')', ']', '}']
    let arr = []
    //console.log(closing.indexOf(braces[")"]) === opening.indexOf(arr[")"]))
    for (let i = 0; i < braces.length; i++) {
        if (opening.includes(braces[i])) {
            arr.push(braces[i])
        } else
        if (closing.indexOf(braces[i]) === opening.indexOf(arr[arr.length - 1])) {
            arr.pop()
        } else return false
    } return arr.length === 0;
}

I was clearly overthinking it in the first place haha. Thanks for everyone that helped!

Answer 4

var validBraces = (s) => {
    let objO  = {'(': 0, '[': 1, '{': 2};
    let objC  = {')': 0, ']': 1, '}': 2};
    let stack = [];

    for (let i=0; i<s.length; i++) {
        if (objO.hasOwnProperty(s[i])) {
            if (stack.length === 0 || stack[stack.length-1].idx!==objO[s[i]])
                stack.push({idx: objO[s[i]], count: 1});
            else
                stack[stack.length-1].count++;
        }
        else if (objC.hasOwnProperty(s[i])) {
            if (stack.length === 0 || stack[stack.length-1].idx!==objC[s[i]])
                return false;
            else {
                stack[stack.length-1].count--;
                if (stack[stack.length-1].count===0)
                    stack.pop();
            }
        }
    }
    return stack.length === 0;
};

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

Answer 5

As Dave suggested, using a stack, I've wrote the code for it:

var leftBraces="([{";
var rightBraces=")]}";

function checkBraces(braces) {
  var ok=true;
  var stack=[];
  for(var i=0; i<braces.length && ok; i++) {
    var brace=braces[i];
    if(leftBraces.includes(brace)) stack.push(brace);
    else {
      var leftBrace=stack.pop();
      if(leftBrace==undefined) ok=false;
      else if(leftBraces.indexOf(leftBrace)!=rightBraces.indexOf(brace)) ok=false;
    }
  }
  if(stack.length) ok=false;
  return ok;
}

Code assumes only braces (no spaces or other characters).
I'm using string.indexOf() that matches for leftBraces and rightBraces.
Also, within the for loop, notice the termination part (2nd): i<braces.length && ok - doesn't "have to" use the iterator and, if I'm not mistaken, can even be empty...