Javascript: Balancing Parentheses

Given a string, that consist of only two types of characters: '(' and ')' . Balance the parentheses by inserting either a '(' or a ')' as many times as necessary. Determine the

Solution 1:

You could take an array for keeping track of the last opening brackets and remove one if a closing one is found.

For not found closing brackets, add some other caracter to the array and return the length of the array as result.

functioncheckParanthesis(str) {
    let brackets = [];
    for (let i = 0; i < str.length; i++) {     
        if (str[i] === "(") {
            brackets.push(str[i]);
        } elseif (str[i] === ")") {
            if (brackets[brackets.length - 1] === "(") brackets.pop();
            else brackets.push("#");
        }
    }
    return brackets.length;
}

console.log(checkParanthesis('()))'));

Solution 2:

Here is a solution with recursion, with also a function to correct the original string based on the result

let output = [];

functioncheckParanthesisRec(str, count, curr, iter) {
  if(str.length === 0){
    return {
      count: count,
      correction: iter
    };
  }
  if(str.substr(0,1) === ')'){
    iter[curr] = '(';
    count++
  }else{
    var closing = str.indexOf(')');
    if(closing != -1){
      str = str.substr(0, closing) + str.substr(closing+1);
    }else{
      iter[curr] = ')';
      count++
    }
  }
  returncheckParanthesisRec(str.substr(1), count, curr+1, iter);
}

functioncheckParanthesis(str){
  returncheckParanthesisRec(str, 0, 0, {});
}

var test = '()))';
var res = checkParanthesis(test);

console.log(res.count);

functioncorrectParenthesis(str, correction){
  var invertedPositions = Object.keys(correction).map((k) =>parseInt(k)).sort(function(a, b){return b-a});
  invertedPositions.forEach((p) => {
     str = str.substr(0, p) + correction[p] + str.substr(p);
  });
  return str;
}

console.log(correctParenthesis(test, res.correction));

Solution 3:

A simpler(?) approach:

functioncountMissingParenthese(parenthesesString) {
  var temp=parenthesesString;
  var temp2="";
  var done=false;
  while(!done) {
    temp2=temp.split("()").join("");
    done=(temp2.length==temp.length);
    temp=temp2;
  }
  console.log(temp);
  return temp.length;
}

The function removes "()"s, logs what's left, and returns how many left. It does not tell you which are missing and where - but you didn't ask for it.

---

Note to possible down-voters: Please explain why in detail instead. Don't be a troll. Thank you!

Solution 4:

The simple solution in JavaScript

/**
 * @param {string} s
 * @return {boolean}
 */var checkParanthesis = function(s) {
    if(typeof s !== "string" || s.length % 2 !== 0) returnfalse;
    let i = 0;
    let arr = [];
    while(i<s.length) {
        if(s[i]=== "{" || s[i]=== "(" || s[i]=== "[") {
           arr.push(s[i]);
        } elseif(s[i] === "}" && arr[arr.length-1] === "{") {
            arr.pop()
        } elseif(s[i] === ")" && arr[arr.length-1] === "(") {
            arr.pop()
        } elseif(s[i] === "]" && arr[arr.length-1] === "[") {
            arr.pop()
        } else {
            returnfalse;
        }
        i++
    }
    return arr.length === 0;
};
let str = "{([])}";
console.log(checkParanthesis(str))

Time complexity O(n)

Solution 5:

Optimized Solution in javascript

constisBalanced = (str) => {
let map = {")":"(","}":"{","]":"["}
  let arr = []
  for(let i=0;i<str.length;i++){
    if(Object.keys(map).includes(str[0])){
      returnfalse
    }
    if(Object.values(map).includes(str[i])){
      arr.push(str[i])
    }
    elseif(Object.keys(map).includes(str[i])){
      if(arr[arr.length-1]===map[str[i]]){
        arr.pop()
      }
    }
  }
  return !arr.length

}


console.log(isBalanced("[{()}[]]"))