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 ments: 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 overplicating 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:

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 ments: 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 overplicating 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:

• javascript

• 7 You might be over-thinking it. It boils down to pushing opening braces and popping when see a closing brace, and seeing if they match up. – Dave Newton Commented Jun 23, 2020 at 22:36
• 1 Not really sure if this is allowed or not but the last video I made on my youtube channel I solve exactly this problem: youtube./watch?v=gQl3YrpHbkI&t=88s – Talmacel Marian Silviu Commented Jun 23, 2020 at 22:36
• 1 Does this answer your question? Algorithm: optimizing 'balancing brackets' – user120242 Commented Jun 23, 2020 at 22:58
• 1 Folks, please keep in mind the OP is explicitly trying to solve this for themselves. Pointing at answers or providing solutions, particularly overly-plex ones, is not what they're asking for. – Dave Newton Commented Jun 23, 2020 at 23:12
• 1 @DaveNewton Thanks man! Exactly the kind of hint I was hoping for, I'll try to do what you suggested. – santsleo Commented Jun 24, 2020 at 12:25

5 Answers 5

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!

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...

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("[({})](]"));

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

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