JavaScript: Balancing parentheses

user_12971921 0
Viewed 14094

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 minimum number of characters, that must be inserted. Example s = "(()))". To make it valid sequence should be inserted one "(" at the beginning . Now the string is balanced after one insertion. Answer is 1.

My problem here, in my try is that I make the string valid, but can't determine the minimum number of insertion, that should make the sequence valid.

let output = [];

function checkParanthesis(str) {
  let count = 0;
  for (let i = 0; i < str.length; i++) {
    if (str[i] === "(") {
      output.push(str[i]);
      count++;
    } else if (str[i] === ")") {
      if (output.pop() !== "(") {
        count++
      }
    }
    console.log(count);
  }
  return output.length;
}

checkParanthesis('()))')

javascript
7 Answers

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.

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

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

user_14476750

A simpler(?) approach:

function countMissingParenthese(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!

user_57925090

My Solution

const isValid = function (inputStr) {
    const status = false;
    const map = {
        "(": ")",
        "{": "}",
        "[": "]"
    }
    const char = [];

    for (let a = 0; a < inputStr.length; a++) {
        if (map[inputStr[a]]) {
            char.push(map[inputStr[a]]);
        } else {
            if (char.pop() !== inputStr[a]) {
                return status;
            }
        }
    }

    return char.length === 0;
};

console.log(isValid("{()}(())"));  // true
console.log(isValid("{(}(())"));  // false
user_85204830

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

let output = [];

function checkParanthesisRec(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++
    }
  }
  return checkParanthesisRec(str.substr(1), count, curr+1, iter);
}

function checkParanthesis(str){
  return checkParanthesisRec(str, 0, 0, {});
}

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

console.log(res.count);

function correctParenthesis(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));

user_118294080

The simple solution in JavaScript

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

Time complexity O(n)

user_91926030

Optimized Solution in javascript

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

}


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

user_168076490 
function isBalance(str) {
    let r = /((\()([^\(\)]+)(\)))/g
    str = str.replace(r,'');
    return str.match(/([\(\)]+)/g).length;
}

console.log(isBalance("(sdgs  23424   fg)asd)sds)asdf)asdf(asdf 23 Ã ´  ¨%$$% asdfasdf)asdfasf(sdfasdf)asd(sdfaf(asdfasdf(sdfaf)"));
// RETURN 5
user_170476540
Related