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

user_13599690 0
Viewed 2254

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:

javascript
6 Answers

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!

user_135996900 

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

user_110579880

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

user_57925090

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

Here is my solution:

var isValid = function (s) {
  let charMap = new Map();

  for (let i = 0; i < s.length; i++) {
    charMap.set(s[i], i);
  }

  return Boolean(
    charMap.get("(") < charMap.get(")") &&
    charMap.get("(") % 2 != charMap.get(")") % 2 &&
    charMap.get("{") < charMap.get("}") &&
    charMap.get("{") % 2 != charMap.get("}") % 2 &&
    charMap.get("[") < charMap.get("]") &&
    charMap.get("[") % 2 != charMap.get("]") % 2
  );
};

Explanation:

  1. In order to achieve a quick and short solution, I have identified the common pattern of validity for opening/closing braces.
  2. The common pattern for opening and closing braces' validity is that if say the opening(closing) stands at the even index in the string, the other one should be odd and vice versa. Example {}, {[]}, {()[]}, {[()]}.
  3. Because we want to avoid a double loop for performance reasons, we are using a Hash Table via Map() to store the character and the index.
  4. An alternative for getting the character's index would be using Array's find or another method, but that would end up in a second loop over the values which we want to avoid.
  5. Finally, once the indexes of and the characters are stored in the charMap, we check whether or not the stored closing/opening characters' standing (odd/even) in the string is not equal, e.g. if '(' is odd the ')' should be even and vice versa.
  6. We check this via the remainder (%) operator, i.e. a number's remainder of 2 is 0 if even.
  7. Additionally, we need to check whether the order of braces is correct, e.g. if '(' is before '}';
  8. The Boolean() function coerces the comparisons in the desired result.
user_88895220
Related