检查引号和括号是否平衡

Question

有多种解决方案可以检查括号是否平衡，但我没有找到一个可以检查平衡引号和括号的单一解决方案。

我没有成功地尝试调整此解决方案(codereview - balanced parentheses)，以便能够检查引号和括号是否平衡。

例如，这应该是不平衡的("back-to-school)"

原始代码：

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

我的代码 - 大多数相似 - 但添加了不平衡的报价检查。

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

确定什么是最好的方法对我来说非常棘手。使用括号，您总是知道何时打开或关闭，带引号，而不是那么多。

Answer 1

这将以两种方式检查push()或pop()的"。

• 如果stack为空或堆栈中的最后一个字符不等于"，则将此"插入堆栈。
• 如果stack不为空并且堆栈中的最后一个字符等于"，那么pop()堆栈本身的"。这样做是因为我在这里做了一种贪婪匹配的形式，因为已经堆叠"的"意味着在"..."内部的表达被评估。所以，我们可以安全地匹配这两个"并继续下一个。

运作良好，但如果任何情况下失败，请告诉我。

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

Answer 2

你可以尝试在堆栈上放置一个有序的元组并根据它进行检查。

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

== ("")("") 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

我太累了，实际上没有实现这个，但希望它给了你一些想法和说明性的例子，我会在睡觉后重温它。

Answer 3

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