BALANCED PARENTHESES PROBLEM ASKED BY GOOGLE

BalancedParenthesesProblem.txt

PROBLEM STATEMENT: You're given a string consisting solely of (, ), and *. * can represent either a (, ), or an empty string. Determine whether the parentheses are balanced.

SOLUTION IN JAVASCRIPT(JS):

var str = "((*(*)))"; // User Input.
var arr = str.split(''); // Make array from user string.
var stack = {}; // Make an empty stack.
var balance = true; // Let given string has balanced parentheses.

// Loop through the arr array.
for (let count = 0; count < arr.length; count++) {
  if (!setVal(arr[count])) {
    balance = false;
    break;
  }
}

if (balance) {
  balance = checkStack();
}

console.log(`Given String is ${balance ? 'balanced' : 'not balanced'}`);

/*
 * addChar function add 1 to each stack as we see '(' character.
 */
function addChar() {
  if (Object.keys(stack).length == 0) {
    // run very first time.
    stack['0'] = 1;
  } else {
    for (key in stack) {
      stack[key]++;
    }
  }
  return true;
}

/*
 * removeChar function subtract 1 from each stack as we see ')' character.
 */
function removeChar() {
  if (Object.keys(stack).length == 0) {
  // run when there we see ')' as very first character.
    return false;
  } else {
    for (key in stack) {
      stack[key]--;
    }
  }
  // Check all the stacks are empty or not.
  // If any stack has a value equal or greater than 0 it means we can procces further.
  for (key in stack) {
    if (stack[key] >= 0) {
      return true;
    }
  }
  // if each stack has less than 0 i.e. there is no '(' character corresponding to ')' character.
  return false;
}

/*
 * addAsterisk function add '2*currentStacks' stack into currentStacks.
 */
 
function addAsterisk() {
  let currentStackLength = Object.keys(stack).length;
  let keyPos = currentStackLength;
  if (currentStackLength == 0) {
    stack['0'] = 1;
  } else {
    for (let count = 0; count < currentStackLength; count++) {
      // If * is treated as '(' character.
      stack[keyPos] = stack[count] + 1;
      keyPos++;
      // If * is treated as ')' character.
      stack[keyPos] = stack[count] - 1;
      keyPos++;
    }
  }
  return true;
}

/*
 * setVal function call the character corresponding function.
 */
function setVal(char) {
  if (char == '(') {
    return addChar();
  } else if (char == ')') {
    return removeChar();
  } else {
    // this will run for '*' character.
    return addAsterisk();

  }
}

function checkStack() {
  // Check any stacks is empty or not.
  // If any stakc is empty i.e given string is balanced.
  for (key in stack) {
    if (stack[key] == 0) {
      return true;
    }
  }
  return false;
}