Reputation: 4102

Check if quotes and parentheses are balanced

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.

Upvotes: 2

Answers (6)

trincot

Reputation: 350310

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]}`);
}

Upvotes: 0

Md Abdul Halim Rafi

Reputation: 1970

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

Upvotes: -1

Abhimanyu

Reputation: 114

   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;
}

Upvotes: -2

Amit

Reputation: 46323

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)")'));

Upvotes: 3

nice_dev

Reputation: 17805

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

Upvotes: 2

cyniikal

Reputation: 134

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.

Upvotes: 2

Check if quotes and parentheses are balanced

Answers (6)

Related Questions