Все допустимые комбинации 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
,
- Редукция начинается с 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 ())(()