代码之家 › 专栏 › 技术社区 › codeepic zetriks

检查引号和括号是否平衡

algorithm javascript

codeepic zetriks · 技术社区 · 6 年前

我一直在尝试采用这个解决方案,但没有成功 (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;
}

3 回复 | 直到 6 年前

nice_dev 6 年前

这将检查 push() 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]);
}

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

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

cyniikal 6 年前

你可以试着把一个有序的元组放在堆栈上并以此为基础进行检查。

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

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

我实在太累了,无法真正实现它,但希望它能给你一些想法和说明性的例子,我会在睡了一觉后再看一遍。

-1

Abhimanyu 5 年前

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