如何在 JavaScript 中检查有效的括号，编程问题？

Question

最近几天我一直在与codewars上的以下问题苦战：

编写一个函数，接受一个括号字符串，并确定括号顺序是否有效。如果字符串有效，它应该返回 true，如果无效则返回false。

所有输入字符串都将是非空的，并且仅由圆括号、方括号和花括号组成：()[]{}。

什么被认为是有效的？

如果所有括号都与正确的括号匹配，那么括号字符串就被认为是有效的。

例子

"(){}[]"   =>  True
"([{}])"   =>  True
"(}"       =>  False
"[(])"     =>  False
"[({})](]" =>  False

我在这个代码上真的卡住了，目前的代码如下：

function validBraces(braces){
    let opening = [ '(', '[', '{']
    let closing = [ ')', ']', '}']
    let count = 0
    const left = []
    const right = []

    // I generate left and right arrays, left w/the opening braces from the input, right w/ the closing
    for (let i = 0; i < braces.length; i++) {
        if (opening.includes(braces[i])) {
            left.push(braces[i])
        } else if (closing.includes(braces[i])) {
            right.push(braces[i])
        }
    }
    if (braces.length % 2 !== 0) {
        return false
    }
    // I know there's no point in doing this but at one point I thought I was finishing the program and thought I would 'optimize it' to exit early, probably this is dumb haha.
    if (left.length !== right.length) {
        return false
    }
    // The juicy (not juicy) part where I check if the braces make sense
    for (let i = 0; i < left.length; i++) {
    // If the list are made up of braces like  ()[]{} add one to counter
        if (opening.indexOf(left[i]) === closing.indexOf(right[i])) {
            count += 1
        } else // If left and right are mirrored add one to the counter
            if (opening.indexOf(left[i]) === closing.indexOf(right.reverse()[i])) {
                count += 1
            }
}
    //If the counter makes sense return true
    if (count === braces.length / 2) {
        return true
    } else { return false}
}


console.log(validBraces( "()" )) //true
console.log(validBraces("([])")) //true
console.log(validBraces( "[(])" )) //false
console.log(validBraces( "[(})" )) //false
console.log(validBraces( "[([[]])]" )) //true

一些评论：我知�我还没有检查这个例�（[]）（） ，但我想以��方�将其拆分为两个较�的检查。

如�您读到这里，谢谢您。我会感激任何形�的指导，尽管我�希望有人替我解决这个问题。如�我过���化了这个问题，因为它是一个6级难度的问题，所以如何更��地解决它的�示将�常�欢�。

��致谢���

- santsleo

---

你可能想太多了。这其实很简单，就是在遇到左括号时压入栈中，在遇到右括号时弹出栈，并检查它们是否匹配。 - Dave Newton

不太确定是否允许，但我在我的YouTube频道上制作的最后一个视频中解决了这个问题：https://www.youtube.com/watch?v=gQl3YrpHbkI&t=88s - Talmacel Marian Silviu

这个回答解决了你的问题吗？算法：优化'平衡括号' - user120242

请注意，楼主明确表示要自己解决这个问题。指向答案或提供解决方案，特别是过于复杂的方案，不是他们所要求的。 - Dave Newton

@DaveNewton 谢谢你！这正是我所期望的提示，我会尝试按照你的建议去做。 - santsleo

Answer 1

太好了！我终于通过这里给我的一些提示自己找到了解决方案：

function validBraces(braces){
    let opening = [ '(', '[', '{']
    let closing = [ ')', ']', '}']
    let arr = []
    //console.log(closing.indexOf(braces[")"]) === opening.indexOf(arr[")"]))
    for (let i = 0; i < braces.length; i++) {
        if (opening.includes(braces[i])) {
            arr.push(braces[i])
        } else
        if (closing.indexOf(braces[i]) === opening.indexOf(arr[arr.length - 1])) {
            arr.pop()
        } else return false
    } return arr.length === 0;
}

我在一开始明显想得太多了，哈哈。谢谢所有帮助我的人！

- santsleo

---

很高兴你解决了它 :) 唯一真正的“问题”（考虑到限制，不算什么问题）是这里有很多“隐藏”的迭代（includes和多个indexOf）。这就是为什么你会看到很多解决方案使用对象或Map。但是，正如我最近所学到的，使用对象/映射可能会在小集合上产生性能损失，因此我猜这实际上比基于映射的解决方案更快，尽管我没有测试过。 - Dave Newton

底线是，做得好，热情好，你花时间去琢磨并发布答案真的很不错。如果可以的话，我会点赞两次的。 - Dave Newton

不要忘记你可以将你的答案标记为被接受的答案！非常好的实现！ - phentnil

Answer 2

var validBraces = (s) => {
    let objO  = {'(': 0, '[': 1, '{': 2};
    let objC  = {')': 0, ']': 1, '}': 2};
    let stack = [];

    for (let i=0; i<s.length; i++) {
        if (objO.hasOwnProperty(s[i])) {
            if (stack.length === 0 || stack[stack.length-1].idx!==objO[s[i]])
                stack.push({idx: objO[s[i]], count: 1});
            else
                stack[stack.length-1].count++;
        }
        else if (objC.hasOwnProperty(s[i])) {
            if (stack.length === 0 || stack[stack.length-1].idx!==objC[s[i]])
                return false;
            else {
                stack[stack.length-1].count--;
                if (stack[stack.length-1].count===0)
                    stack.pop();
            }
        }
    }
    return stack.length === 0;
};

console.log(validBraces("(){}[]"));
console.log(validBraces("([{}])"));
console.log(validBraces("(})"));
console.log(validBraces("[(])"));
console.log(validBraces("[({})](]"));

- Rahul Bhobe

---

似乎有点过度设计。 - Dave Newton

Answer 3

正如Dave建议的那样，使用一个栈，我已经为此编写了代码：

var leftBraces="([{";
var rightBraces=")]}";

function checkBraces(braces) {
  var ok=true;
  var stack=[];
  for(var i=0; i<braces.length && ok; i++) {
    var brace=braces[i];
    if(leftBraces.includes(brace)) stack.push(brace);
    else {
      var leftBrace=stack.pop();
      if(leftBrace==undefined) ok=false;
      else if(leftBraces.indexOf(leftBrace)!=rightBraces.indexOf(brace)) ok=false;
    }
  }
  if(stack.length) ok=false;
  return ok;
}

代码假定只有大括号（没有空格或其他字符）。
我正在使用string.indexOf()查找leftBraces和rightBraces。
此外，在for循环中，请注意终止部分（第2个）：i<braces.length && ok - 不必使用迭代器，如果我没记错的话，甚至可以为空...

- iAmOren

---

那么，你能否给好的答案点赞并选择最佳答案呢？ 希望是我的... :) - iAmOren

在Javascript中验证括号是否匹配。简单且被接受的解决方案 https://stackoverflow.com/questions/51822125/check-if-quotes-and-parentheses-are-balanced/74582824#74582824 - Ashish

Answer 4

function validBraces(braces){
    let par =0;
    let bra =0;
    let cur =0;
    for(let i =0; i<braces.length; i++){
        if(braces[i]==="("){
            par++;
        }
        if(braces[i]===")"){
            par--;
        }
        if(braces[i]==="["){
            bra++;
        }
        if(braces[i]==="]"){
            bra--;
        }
        if(braces[i]==="{"){
            cur++;
        }
        if(braces[i]==="}"){
            cur--;
        }
    }

    if(par<0 || bra<0 || cur<0){
        return false;
    } 
    return true;
};

- codingpractice2008

---

如果您使用 switch 语句而非所有这些 if 语句，您的代码将会更加优秀。 - Lee Taylor

Answer 5

这里是一个简化的解决方案：

let isMatchingBraces = function(str) {
    let stack = [];
    let symbol = {
        '(': ')',
        '[': ']',
        '{': '}'
    };
    for (let i = 0; i < str.length; i += 1) {
        // If character is an opening brace add it to a stack
        if (str[i] === '(' || str[i] === '{' || str[i] === '[') {
            stack.push(str[i]);
        }
        //  If that character is a closing brace, pop from the stack, which will also reduce the length of the stack each time a closing bracket is encountered.
        else {
            let last = stack.pop();
            //If the popped element from the stack, which is the last opening brace doesn’t match the corresponding closing brace in the symbol, then return false
            if (str[i] !== symbol[last]) {
                return false
            };
        }
    }
    // After checking all the brackets of the str, at the end, the stack is not 
    // empty then fail
    if (stack.length !== 0) {
        return false
    };
    return true;
}

- Govind

---

在Javascript中验证括号是否匹配。简单且被接受的解决方案 https://stackoverflow.com/questions/51822125/check-if-quotes-and-parentheses-are-balanced/74582824#74582824 - Ashish

Answer 6

这是我的解决方案：

var isValid = function (s) {
  let charMap = new Map();

  for (let i = 0; i < s.length; i++) {
    charMap.set(s[i], i);
  }

  return Boolean(
    charMap.get("(") < charMap.get(")") &&
    charMap.get("(") % 2 != charMap.get(")") % 2 &&
    charMap.get("{") < charMap.get("}") &&
    charMap.get("{") % 2 != charMap.get("}") % 2 &&
    charMap.get("[") < charMap.get("]") &&
    charMap.get("[") % 2 != charMap.get("]") % 2
  );
};

解释：

1. 为了实现快速简短的解决方案，我已经确定了打开/关闭括号有效性的常见模式。
2. 打开和关闭括号有效性的常见模式是，如果说在字符串中打开（关闭）的位置处于偶数索引，则另一个位置应该是奇数索引，反之亦然。例如{}, {[]}, {()[]}, {[()]}。
3. 因为我们想要避免双重循环以提高性能，所以我们使用哈希表通过Map()来存储字符和索引。
4. 获取字符索引的另一种方法是使用数组的find或其他方法，但这将导致对我们想要避免的值进行第二次循环。
5. 最后，一旦字符的索引和字符被存储在charMap中，我们检查存储的关闭/打开字符的位置（奇数/偶数）是否相等，例如如果'('是奇数，则')'应该是偶数，反之亦然。
6. 我们通过余数(%)运算符来检查这个问题，即一个数字的余数为2时，如果是偶数则为0。
7. 此外，我们还需要检查括号的顺序是否正确，例如如果'('在'}'之前；
8. Boolean()函数强制执行所需结果的比较。

- Aramayis Galichyan

---

感谢您提供这段代码片段，它可能会提供一些有限的、即时的帮助。一个适当的解释将极大地提高其长期价值，因为它展示了为什么这是一个好的问题解决方案，并使其对未来读者有其他类似问题的人更有用。请[编辑]您的答案以添加一些解释，包括您所做的假设。 - Giorgio Tempesta

@GiorgioTempesta，谢谢。添加解释。 - Aramayis Galichyan