Все допустимые комбинации n-пары круглых скобок

  • Я учусь JS сейчас..
    • Я пытаюсь написать простую программу JS..
    • то, что я пытаюсь сделать, это напечатать все допустимые комбинации n-пары скобок (правильно открыт и закрыт)
    • например (), (() ()), (())
    • я написал логику, вы можете сказать мне, правильно ли это или нет

https://jsfiddle.net/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;
    }

  }

}());

4 ответа

Проверка неверна, но Вы можете легко это исправить: на каждом этапе for В цикле количество открывающих скобок не может быть меньше количества закрывающих скобок:

if (rightCount < leftCount)
    return false;

Вся функция должна выглядеть так:

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

Если вы хотите сгенерировать все допустимые строки, вы можете использовать эту функцию:

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):
// ["()()()", "()(())", "(())()", "(()())", "((()))"]

Ваша функция неверна, попробуйте проверить, если слева и справа скобки и сбалансированы:

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 - использовать replace() удалить любые символы, которые не являются ( или же ),
  • split('') - возвращает массив, чтобы мы могли использовать reduce,
  • reduce() - применяет функцию к аккумулятору, и каждое значение массива (слева направо) должно сводить его к одному значению.
    • Редукция начинается с 0 в качестве начального значения, а в функции редукции мы считаем скобки
      (+1 за (, -1 за ))
    • Наша строка действительна, если наш счетчик никогда не опускается ниже 0 и мы в конечном итоге 0,

Вы также можете написать функцию приведения так:

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

  return -1;
}

Это эквивалентно:

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

Попробуйте, я немного изменил ваш код. Модификация и ее объяснение отмечены в комментариях.

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


  }

}());

Это неправильно, потому что ваша функция вернет true для этого примера))((или this ())(()

Другие вопросы по тегам