javascript 检查引号和括号是否对称

jdzmm42g  于 2022-11-27  发布在  Java
关注(0)|答案(6)|浏览(179)

检查圆括号是否对称有多种解决方案,但我还没有找到一种既检查对称引号又检查圆括号的解决方案。
我一直在尝试调整这个解决方案(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;
}

对于我来说,确定什么是最好的方法是相当棘手的。使用括号,你总是知道一个是开还是闭,使用引号,就不那么多了。

ztyzrc3y

ztyzrc3y1#

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

prdp8dxp2#

这会以两种方式执行push()"pop()检查。

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

工作很好,但让我知道,如果它失败的任何情况。

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
siv3szwd

siv3szwd3#

您可以尝试将一个有序元组放在堆栈上,并基于此进行检查。

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

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

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

igetnqfo

igetnqfo4#

我建议通过删除所有带引号的子字符串来简化输入。引号的行为不同,因为引号内的括号没有被特殊处理,而是作为普通字符处理。通过首先删除每个带引号的部分,这个“问题”从一开始就解决了。还有不相关的字符(既不是圆括号也不是引号)。这样,我们只剩下一个带有括号的字符串,并且可能只出现一个引号,后者会立即使输入无效。
下面的代码类似于@nice_dev的答案,实现了该操作,并将pairs取反;它还将撇号作为可选分隔符来处理:

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

eblbsuwk5#

一个简单的处理方法可能是这样的,只针对第一个大括号:

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
sc4hvdpw

sc4hvdpw6#

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

相关问题