CODEWITHSUNDEEP
javascriptarrays
katty
katty

Reputation: 173

Finding if a given set of parentheses is valid or not

Below is my code, it works for some strings but not for all. Ex: "()()()()()((" expected is false, my code returns true.

function validParentheses(parens){
    var stack = [];

    parens.split('').map((cur, index) =>{
        if(stack.length === 0 || stack[index-1] === cur) stack.push(cur);
        else stack.pop();
  }); 

  return stack.length > 0 ?  false : true;
}

Upvotes: 0

Views: 291

Answers (5)

Nina Scholz
Nina Scholz

Reputation: 386654

You need to check the last added value as well, because an unresolves closing bracket should remain in he stack.

BTW, Array#forEach is the method of choice, because Array#map returns a new array, which is not used here.

function validParentheses(parens) {
    var stack = [];

    parens.split('').forEach((cur, index) => {
        if (cur === ')' && stack[stack.length - 1] === '(') stack.pop();
        else stack.push(cur);
    });

    return !stack.length;
}

console.log(validParentheses("(())()"));
console.log(validParentheses("()()()()()(("));
console.log(validParentheses("))(())"));

Upvotes: 1

David Revel
David Revel

Reputation: 11

in stack[index-1] === cur you are comparing if the char isn't the same like the one stored in the stack, so )( opposite parens will be valid

you can try do something like this

function validParentheses(parens) {
    if (parens % 2 == 1) return false;
    for (let i = 0; i < parens.length; i++) {
        const char = parens[i];
        if (char == "(") {
            if (parens[i + 1] == ")") {

                i++;
            } else {
                return false
            }
        } else {
            return false
        }
    }
    return true;
}

Upvotes: 1

Victory
Victory

Reputation: 5890

For every '(' there must be a exactly one ')'. So you need a counter to see that there is an exact match

function validParentheses(parens){
   
   const chars = parens.split('');
   const numChars = chars.length;
   
   let ii;
   let numOpenParens = 0;
   for (ii = 0; ii < numChars; ii += 1) {
       curChar = chars[ii];
       numOpenParens += curChar == '(' ? 1 : -1;
       // return false if there is one too many closed parens
       if (numOpenParens < 0) {
          return false;
       } 
   }

   // return true only if all parens have been closed
   return numOpenParens === 0;

}

Upvotes: 2

hgb123
hgb123

Reputation: 14891

For case when stack's length is greater than 0:

  • if top of the stack is equal to current iterated parenthesis, push that to stack
  • else pop the stack

function validParentheses(parens) {
  var stack = []

  parens.split("").forEach((cur) => {
    if (stack.length > 0) {
      if (stack[stack.length - 1] === cur) {
        stack.push(cur)
      } else {
        stack.pop()
      }
    } else {
      stack.push(cur)
    }
  })

  return stack.length > 0 ? false : true
}

console.log(validParentheses("()()()()()(("))
console.log(validParentheses("()()()()()()"))
console.log(validParentheses("((()))"))
console.log(validParentheses("((())))"))

Upvotes: 1

Taplar
Taplar

Reputation: 24965

stack[index - 1] will be valid so long as you push every iteration. In the case that you pop an element, the incrementing index will always be out of bounds.

Change it to stack.length - 1 to always get the last element, regardless of what is pushed or popped.

Upvotes: 3

Related Questions