javascript - all valid combinations of n-pair of parenthesis - Stack Overflow

admin管理员组

文章数量:1416306

I'm trying to write a js program to print all valid binations of n pairs of parentheses, eg:

(), (()()),(()).

Can you tell me whether this is correct or not?

/

module.exports = Parentheses = (function() {
  var _isParenthesesMatch = function(str) {
    var parentheses = str.length;
    var rightParentheses = '(';
    var leftParentheses = ')';
    var rightCount = 0;
    var leftCount = 0;

    for(i=0;i<=str.length;i++){
       if(rightParentheses == str.charAt(i))
       {
          rightCount++;
       }
       else if(leftParentheses == str.charAt(i))
       {
          leftCount++;
       }
    }

    if(rightCount == leftCount){
      return true;
    }
    else(rightCount != leftCount){
      return false;
    }

  }
  
}());

I'm trying to write a js program to print all valid binations of n pairs of parentheses, eg:

(), (()()),(()).

Can you tell me whether this is correct or not?

https://jsfiddle/e7mcp6xb/

module.exports = Parentheses = (function() {
  var _isParenthesesMatch = function(str) {
    var parentheses = str.length;
    var rightParentheses = '(';
    var leftParentheses = ')';
    var rightCount = 0;
    var leftCount = 0;

    for(i=0;i<=str.length;i++){
       if(rightParentheses == str.charAt(i))
       {
          rightCount++;
       }
       else if(leftParentheses == str.charAt(i))
       {
          leftCount++;
       }
    }

    if(rightCount == leftCount){
      return true;
    }
    else(rightCount != leftCount){
      return false;
    }

  }
  
}());

• javascript

Share Improve this question Follow edited May 5, 2023 at 18:10 meetar 7,63188 gold badges4343 silver badges7474 bronze badges asked Mar 28, 2015 at 18:38 user4640064user4640064

Add a ment  | 

4 Answers 4

Sorted by: Reset to default 7

The check is wrong, but You can fix it easily: In each step of the for loop the number of opening parenthesis cannot be smaller than the number of closing ones:

if (rightCount < leftCount)
    return false;

The whole function should look like this:

function(str) {
    var rightParentheses = '(';
    var leftParentheses = ')';
    var rightCount = 0;
    var leftCount = 0;

    for (var i = 0; i <= str.length; i++) {
       if (rightParentheses == str.charAt(i))
          rightCount++;
       else if (leftParentheses == str.charAt(i))
          leftCount++;

       if (rightCount < leftCount)
          return false;
    }

    return rightCount == leftCount;
}

If You'd like to generate all valid strings, you can use this function:

function nPair(n) {
    if (n == 0)
        return [""];

    var result = [];
    for (var i = 0; i < n; ++i) {

        var lefts = nPair(i);
        var rights = nPair(n - i - 1);

        for (var l = 0; l < lefts.length; ++l)
            for (var r = 0; r < rights.length; ++r)
                result.push("(" + lefts[l] + ")" + rights[r]);
    }

    return result;
}

// result of nPair(3):
// ["()()()", "()(())", "(())()", "(()())", "((()))"]

Try this, i have modified your code a little bit. Modification and its explanation is marked in ments.

module.exports = Parentheses = (function() {
  var _isParenthesesMatch = function(str) {
    var parentheses = str.length;
    var rightParentheses = '(';
    var leftParentheses = ')';
    var count=0;

    for(i=0;i<str.length;i++){
        //this is to check valid bination start always from ( and end with )
            if(str.charAt(0)==rightParentheses && str.length-1==leftParentheses) 
            {
               if(rightParentheses == str.charAt(i))
               {
                  count++;  //this will calculate how many times rightParentheses is present & increment count by 1
               }
               else if(leftParentheses == str.charAt(i))
               {
                  count--;  //this will simply decrement count to match valid sequence
               }
            }

            if(count==0){
              return true;
            }


  }

}());

Your function is wrong, try checking if left and right parenthesis and balanced:

function isValid(str){
  var stripedStr = str.replace(/[^\(\)]+/g, '');

  return stripedStr.split('').reduce(function(a, b){
    return a > -1 ? b === '(' ? a + 1 : a - 1 : -1;
  }, 0) === 0;
}

• stripedStr - use replace() to remove any characters that are not ( or ).
• split('') - returns an array so we can use reduce.
• reduce() - applies a function against an accumulator and each value of the array (from left-to-right) has to reduce it to a single value.
  • The reduce starts with 0 as initial value and in the reduce function we count parenthesis
    (+1 for (, -1 for ) )
  • Our string is valid if our counter never goes below 0 and we end up with 0.

---

You can write the reduce function like this too:

function(previousValue, currentValue){
  if (previousValue > -1){
    if (currentValue === '('){
      return previousValue + 1;
    } else {
      return previousValue - 1;
    }
  }

  return -1;
}

This is equivalent to:

function(a, b){
  return a > -1 ? b === '(' ? a + 1 : a - 1 : -1;
}

It is wrong, because your function will return true for this example ))(( or this ())(()

本文标签： javascriptall valid combinations of npair of parenthesisStack Overflow