There are multiple solutions to how to check if parentheses are balanced, but I haven't found a single one that would be checking both for balanced quotes and parentheses.

I have been unsuccessfully trying to adapt this solution (codereview - balanced parentheses) to be able to check if the quotes and parentheses are balanced.

For example this should be unbalanced ("back-to-school)"

Original code:

function parenthesesAreBalanced(string) {
  var parentheses = "[]{}()",
    stack = [],
    i, character, bracePosition;

  for(i = 0; character = string[i]; i++) {
    bracePosition = parentheses.indexOf(character);

    if(bracePosition === -1) {
      continue;
    }

    if(bracePosition % 2 === 0) {
      stack.push(bracePosition + 1); // push next expected brace position
    } else {
      if(stack.length === 0 || stack.pop() !== bracePosition) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

My code - mostly similar - but added an unbalanced quotes check.

function areQuotesAndParenthesesBalanced(s: string): boolean {
  const parens = '[]{}()',
      parensStack = [];
  let index, char, numOfQuotes = 0;

  for (index = 0; char = s[index++];){
      const bracePosition = parens.indexOf(char);
      let braceType;

    if (bracePosition === -1 && char !== '"')
        continue;

    braceType = bracePosition % 2 ? 'closed' : 'open';

    //check for double quotes mixed with parentheses
    if(char === '"'){
        const lastInStack = parensStack[parensStack.length - 1];

        numOfQuotes++;

        if(lastInStack === '"'){
            numOfQuotes--;
            parensStack.pop();
        }else if(numOfQuotes > 0 && lastInStack !== '"'){
            return false;
        }else{
            parensStack.push('"');
        }
    }

    if (braceType === 'closed') {
        if (!parensStack.length || parens.indexOf(parensStack.pop()) != bracePosition - 1)
            return false;
    } else {
        parensStack.push(char);
    }
}

//If anything is left on the stack <- not balanced
return !parensStack.length;
}

It is quite tricky for me to determine what's the best approach. With parentheses, you always know when one is open or closed, with quotes, not so much.

There are multiple solutions to how to check if parentheses are balanced, but I haven't found a single one that would be checking both for balanced quotes and parentheses.

I have been unsuccessfully trying to adapt this solution (codereview - balanced parentheses) to be able to check if the quotes and parentheses are balanced.

For example this should be unbalanced ("back-to-school)"

Original code:

function parenthesesAreBalanced(string) {
  var parentheses = "[]{}()",
    stack = [],
    i, character, bracePosition;

  for(i = 0; character = string[i]; i++) {
    bracePosition = parentheses.indexOf(character);

    if(bracePosition === -1) {
      continue;
    }

    if(bracePosition % 2 === 0) {
      stack.push(bracePosition + 1); // push next expected brace position
    } else {
      if(stack.length === 0 || stack.pop() !== bracePosition) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

My code - mostly similar - but added an unbalanced quotes check.

function areQuotesAndParenthesesBalanced(s: string): boolean {
  const parens = '[]{}()',
      parensStack = [];
  let index, char, numOfQuotes = 0;

  for (index = 0; char = s[index++];){
      const bracePosition = parens.indexOf(char);
      let braceType;

    if (bracePosition === -1 && char !== '"')
        continue;

    braceType = bracePosition % 2 ? 'closed' : 'open';

    //check for double quotes mixed with parentheses
    if(char === '"'){
        const lastInStack = parensStack[parensStack.length - 1];

        numOfQuotes++;

        if(lastInStack === '"'){
            numOfQuotes--;
            parensStack.pop();
        }else if(numOfQuotes > 0 && lastInStack !== '"'){
            return false;
        }else{
            parensStack.push('"');
        }
    }

    if (braceType === 'closed') {
        if (!parensStack.length || parens.indexOf(parensStack.pop()) != bracePosition - 1)
            return false;
    } else {
        parensStack.push(char);
    }
}

//If anything is left on the stack <- not balanced
return !parensStack.length;
}

It is quite tricky for me to determine what's the best approach. With parentheses, you always know when one is open or closed, with quotes, not so much.

• javascript
• algorithm

• 1 The solution should be the exact same no matter what symbol you're using, just also checks for quotes in the same way you would check for brackets – Mitch Commented Aug 13, 2018 at 12:37
• 2 @Mitchel0022 - I have already tried that and it doesn't work due to how the original solution checks for open closed brackets - you can't discern whether the quote is opening or closing using the same logic. – codeepic Commented Aug 13, 2018 at 12:40
• Your specification is inplete. Do you want to check balance of parentheses inside quoted strings? Is ("])}") a valid string? – Jim Mischel Commented Aug 13, 2018 at 14:46
• Just change var parentheses = "[]{}()" to var parentheses = "[]{}()\"\"", same logic – Mitch Commented Aug 13, 2018 at 14:50
• @Mitchel0022 - that was the first thing I tried - I already told you it ain't working. – codeepic Commented Aug 13, 2018 at 15:06

6 Answers 6

function tokensAreBalanced(string) {
  var asymmetricTokens = "[]{}()",
    symmetricTokens = '"',
    stack = [],
    i, character, tokenPosition;

  for(i = 0; character = string[i]; i++) {
    tokenPosition = asymmetricTokens.indexOf(character);

    if(tokenPosition >= 0) {
      if(tokenPosition % 2 === 0) {
        stack.push(asymmetricTokens[tokenPosition + 1]); // push next expected token
      } else if(stack.length === 0 || stack.pop() !== character) {
        return false;
      }
    } else {
      if(symmetricTokens.includes(character)) {
        if(stack.length > 0 && stack[stack.length - 1] === character) {
          stack.pop();
        } else {
          stack.push(character);
        }
      }
    }
  }

  return stack.length === 0;
}


console.log('("back-to-school)"', tokensAreBalanced('("back-to-school)"'));

console.log('("back-to-school)', tokensAreBalanced('("back-to-school)'));

console.log('("back-to-school")', tokensAreBalanced('("back-to-school")'));

console.log('(ele AND car) OR ("ele car)")', tokensAreBalanced('(ele AND car) OR ("ele car)")'));

This performs a check for push() or pop() of " in 2 ways.

• If stack is empty or last character in stack does not equal ", then insert this " into stack.

• If stack is not empty and last character in stack is equal to ", then pop() the " in stack itself. This is done because I do a form of greedy matching here since a " for already stack " means expression inside "..." was evaluated. So, we are safe to match these 2 " and proceed with the next.

Works well, but let me know if it fails for any case.

function areQuotesAndParenthesesBalanced(s){
	var pairs = {
		'}':'{',
		']':'[',
		')':'(',
	};

	var stack = [];

	for(var i = 0;i < s.length;++i){
		switch(s.charAt(i)){
			case '[': case '{':case '(':
				stack.push(s.charAt(i));
			break;
			case ']': case '}':case ')':
				if(isStackEmpty(stack) || peek(stack) !== pairs[s.charAt(i)]) return false;
				stack.pop();
			break;
			case '"':
				if(isStackEmpty(stack) || peek(stack) !== s.charAt(i)){
					stack.push(s.charAt(i));
				}else{
					stack.pop();
				}
		}
	}

	return isStackEmpty(stack);
}

function isStackEmpty(s){
	return s.length === 0;
}

function peek(s){
	return s[s.length-1];
}


var tests = {
				'("back-to-school")':true,
				'"(back-to-school)"':true,
				'("back-to-school)"':false,
				'("back-to-school)':false,
				'"["["["[]"]"]"]"':true,
				'"["]""':false,
				'"[]"""':true,
				'""""':true,
				'""':true,
				'"':false,
				'""[("")]""':true,
				'""[("")]':true,
				'"["["["[]"]"[""]]"]':false,
				'"[]"[({})]""':true,
				'"[{}"]':false
			};

for(var each_test in tests){
	var res = areQuotesAndParenthesesBalanced(each_test);
	console.log(each_test + " --> " + (res === tests[each_test] ? "ok" : "not ok") + " , expected : " + tests[each_test]);
}

OUTPUT

("back-to-school") --> ok , expected : true
"(back-to-school)" --> ok , expected : true
("back-to-school)" --> ok , expected : false
("back-to-school) --> ok , expected : false
"["["["[]"]"]"]" --> ok , expected : true
"["]"" --> ok , expected : false
"[]""" --> ok , expected : true
"""" --> ok , expected : true
"" --> ok , expected : true
" --> ok , expected : false
""[("")]"" --> ok , expected : true
""[("")] --> ok , expected : true
"["["["[]"]"[""]]"] --> ok , expected : false
"[]"[({})]"" --> ok , expected : true
"[{}"] --> ok , expected : false

You could try putting an ordered tuple on the stack and checking based off of that.

[(,"],
[",)],
[(,"],
[",)]

== ("")("") example of a balanced stack.

[",(],
[",(],
[),"],
[),"]

== "("()")" another balanced stack


[(,"],
[),"]

== (")" trivial unbalanced stack

[(,)] <- trivial item, can ignore in implementation
[","] <- trivial item, can ignore in implementation

[",(],
[),(],
[),"]

== "()()" balanced stack

I'm too tired to actually implement this, but hopefully it gave you some ideas and illustrative examples, I'll revisit it after I get some sleep.

I would suggest simplifying the input by removing all quoted substrings. Quotes behave differently because parentheses inside quotes are not treated specially, but as normal characters. By first removing each quoted part, this "problem" is resolved from the start. Also irrelevant characters (that are not parentheses nor quotes) can be removed as well. That way we are only left with a string that has parentheses and possibly a single occurrence of a quote. The latter would immediately make the input invalid.

Here is code similar to @nice_dev's answer, with that manipulation implemented and with pairs inversed; it also deals with apostrophe as alternative delimiter:

function areQuotesAndParenthesesBalanced(s) {
    const pairs = {
        '{':'}',
        '[':']',
        '(':')',
    };

    const stack = [""]; // Dummy
    for (const token of s.replace(/"[^"]*"|'[^']*'|[^"'{}()[\]]+/g, "")) {
        if (token in pairs) {
            stack.push(pairs[token]);
        } else {
            if (stack.at(-1) !== token) return false;
            stack.pop();
        }
    }
    return stack.length == 1; // Empty
}

// Same tests as in the answer of @nice_dev:
const tests = {
    '("back-to-school")': true,
    '"(back-to-school)"': true,
    '("back-to-school)"': false,
    '("back-to-school)': false,
    '"["["["[]"]"]"]"': true,
    '"["]""': false,
    '"[]"""': true,
    '""""': true,
    '""': true,
    '"': false,
    '""[("")]""': true,
    '""[("")]': true,
    '"["["["[]"]"[""]]"]': false,
    '"[]"[({})]""': true,
    '"[{}"]': false
};

for (const each_test in tests){
    const res = areQuotesAndParenthesesBalanced(each_test);
    console.log(`${each_test} --> ${res === tests[each_test] ? "ok" : "not ok"}, expected: ${tests[each_test]}`);
}

A simple approaching way might be like this for only first braces:

function Search(str) {
    const onlyBrackets = str.replace(/[a-zA-Z]/g, "");
    const left = onlyBrackets.replace(/[)]/g, "");
    const right = onlyBrackets.replace(/[(]/g, "");

    str = left.length === right.length ? 1 : 0
    return str
}

console.log(Search("(coder)(byte))")) // 0

console.log(Search("(c(oder))b(yte)")) // 1

   function isParenthesisBalanced(_str) {
 var parenMap = {'{':'}', '[':']', '(':')'};
 var parenStack =[];

 for(var i=0;i<_str.length; i++) {
     if(_str[i] in parenMap) {
         parenStack.push(_str[i]);
     } else if(Object.values(parenMap).indexOf(_str[i]) != -1) {
        if(parenMap[parenStack.pop()] != _str[i]) return false;
     }
 }
 return true;
}