Correct unbalanced parentheses

Question

Given a string filled with any number of parentheses, find the minimum number of parentheses to be included in the string so that it is valid.

Examples:

• Input "(()()" must return: 1 - "(()())"
• Input "(((" must return: 3 - "((()))"
• Input "())()" must return: 1 - "(())()"

function isBalanced(str) {
  var a = verifica(str)
  var i = 0

  if ( a ) {

    var toRepair,newStr

    toRepair = a == '(' ? ')' : '('

    console.log('str = ', str)

    do {
      newStr = str
      newStr = newStr.substring(0,i)+toRepair+newStr.substring(i)
      console.log( 'newStr = ', newStr)

      i += 1
    } while ( verifica(newStr)  )


    console.log('O certo é: ', newStr)


  } else {
    console.log('ta tudo certo')

  }

}

function verifica(str) {
  var a = str, b
  do { 
    b = a,
    console.log('b = ', b)
    a = a.replace(/\(\)/g, '')
  } while (a != b)

  console.log(a ? 'ta errado' : 'ta certo')

  return a
}



isBalanced('(()()')

https://repl.it/@Aterius/Correct parentesis#index.js

Answer 1

You don’t need regex for that. A simpler way is to count the parentheses. You iterate by the string characters, and if you find a (, increments the counter, and if you find a ), decrease.

There is only one catch: if the string starts with ) for example, you cannot decrease, otherwise the counter will be negative. In this case you have to consider that the ( corresponding, then should account for 1 more for that case.

To another answer said to simply count the amount of ( and ) and subtract from each other, but what if the string is )(? In this case, if we count only and subtract, it will give zero. But I understand that in this case 2 parentheses are missing (one before the ) and another after the (), then it would have to be so:

function quantosParentesesFaltam(str) {
    var naoAbertos = 0, qtd = 0;
    for (var c of str) {
        if (c == '(') { // abriu um parênteses
            qtd++;
        } else if (c == ')') {
            if (qtd == 0) {
                // encontrei um ) sem o ( correspondente
                naoAbertos++;
            } else {
                // fechou o parênteses, diminui o contador pois está ok
                qtd--;
            }
        }
    }
    return qtd + naoAbertos;
}

console.log(quantosParentesesFaltam('(()()')); // 1
console.log(quantosParentesesFaltam('(((')); // 3
console.log(quantosParentesesFaltam('())()')); // 1
console.log(quantosParentesesFaltam(')(')); // 2
console.log(quantosParentesesFaltam(')))(')); // 4
console.log(quantosParentesesFaltam('(()())')); // 0

---

Now if the idea is to tell and fix the string, just adapt the above case to add the missing parentheses in the string:

function conserta(str) {
    var balanceada = str;
    var naoAbertos = 0, qtd = 0;
    for (var c of str) {
        if (c == '(') { // abriu um parênteses
            qtd++;
        } else if (c == ')') {
            if (qtd == 0) {
                // encontrei um ) sem o ( correspondente
                naoAbertos++;
                // adiciona o ( no início
                balanceada = '(' + balanceada;
            } else {
                // fechou o parênteses, diminui o contador pois está ok
                qtd--;
            }
        }
    }
    // adiciona os ) que faltam
    for(var i = 0; i < qtd; i++) {
        balanceada += ')';
    }
    return `${qtd + naoAbertos} - "${balanceada}"`;
}

console.log(conserta('(()()')); // 1 - "(()())"
console.log(conserta('(((')); // 3 - "((()))"
console.log(conserta('())()')); // 1 - "(())()"
console.log(conserta(')(')); // 2 - "()()"
console.log(conserta(')))(')); // 4 - "((()))()"
console.log(conserta('(()())')); // 0 - "(()())"

Basically, if I found a ) without the ( corresponding (which is when the current character is ) and the accountant qtd is zero), I know I have to add one ( at first.

Then at the end of the first for, the accountant qtd will have the amount of ( which have not been closed, so just add that same amount of ) in the end.

---

You can even use regex

Although I find the above solutions much simpler, you can use regex.

Assuming the string has only characters ( and ) (there is no no other different character from these), one idea is to look for pairs of () (namely, a ( followed immediately by a )) and go removing them from the string, until no one.

What is left in the string are the unbalanced ones. So if you have any ) at the beginning, it is because missing add ( at first, and if you have ( at the end, just add ) in the end.

Thus:

function consertaComRegex(str) {
    var r = /\(\)/g;
    var s = str, tmp;
    // enquanto tiver () para ser removido, continua
    while ((tmp = s.replace(r, '')) != s) {
        s = tmp;
    }
    if (s.length == 0) {
        return `0 - "${str}"`;
    }
    // verifica se começa com um ou mais )
    var match = s.match(/^\)+/);
    if (match) { // adiciona os ( que faltam no início
        for(var i = 0; i < match[0].length; i++) str = '(' + str;
    }
    // verifica se termina com um ou mais (
    var match = s.match(/\(+$/);
    if (match) { // adiciona os ) que faltam no final
        for(var i = 0; i < match[0].length; i++) str += ')';
    }
    return `${s.length} - "${str}"`;
}

console.log(consertaComRegex('(()()')); // 1 - "(()())"
console.log(consertaComRegex('(((')); // 3 - "((()))"
console.log(consertaComRegex('())()')); // 1 - "(())()"
console.log(consertaComRegex(')(')); // 2 - "()()"
console.log(consertaComRegex(')))(')); // 4 - "((()))()"
console.log(consertaComRegex('(()())')); // 0 - "(()())"

Answer 2

Your question is not entirely clear. In any situation is it necessary to reorder the characters or just include new ones? In case you don’t have to reorder the characters but only know how many characters, this problem can be solved using a different approach. You can count how many characters '(' and how many characters ')' there is in String and calculate the difference between them. This is the number of characters that need to be inserted to make the String valid:

let numeroCaracteresInseridos = abs(contadorAbre - contadorFecha)