如何验证所有匹配的括号

Question

实现函数 verify(text) 验证文本中的括号是否正确嵌套。你需要考虑三种：(), [], <> 并且只有这几种。示例：

verify("---(++++)----")  -> 1 
verify("") -> 1 
verify("before ( middle []) after ") -> 1  
verify(") (") -> 0 
verify("<(   >)") -> 0 
verify("(  [   <>  ()  ]  <>  )") -> 1 
verify("   (      [)") -> 0

我试着按照下面的方式去做，但面试官说有错误，并给我第二次机会。

function verify(text) {
  const stack = [];
  for (const c of text) {
    if (c === '(') stack.unshift(')')
    else if (c === '[') stack.unshift(']')
    else if (c === '<') stack.unshift('>')
    else if (c === stack[0]) stack.shift()
    else if (c === ')' || c === ']' || c === '>') return 0
  }
  return 1
}


const test_inputs = ["---(++++)----", "", "before ( middle []) after ", ") (", "<( >)", "( [ <> () ] <> )", " ( [)"]
for (const i in test_inputs) {
  console.log(verify(i))
}

输出为：

Answer 1

我们可以使用Array的pop和push功能。当我们遇到 '('、'['、'<' 字符时，我们将压入堆栈。另一方面，当我们遇到')'、']'、'>'时，我们弹出堆栈的最后一个元素。如果找不到这些字符的等价物，我们就确定该字符串无效。最后，如果堆栈中没有剩余元素，则表示该字符串有效。

function verify(text) {
    let stack = [];
    for (const c of text) {
        if (c === '(' || c == '[' || c == '<') {
            stack.push(c);
        } else if (c === ')' || c == ']' || c == '>') {
            if (stack.length == 0) {
                return 0;
            }
            const popValue = stack.pop();
            if (c === ')' && popValue != '(') {
                return 0;
            } else if (c === ']' && popValue != '[') {
                return 0;
            } else if (c === '>' && popValue != '<') {
                return 0;
            }
        }

    }

    if (stack.length > 0) {
        return 0;
    }

    return 1;
}

Answer 2

您的代码唯一的错误是，您在 for 循环中使用了 in 而不是 of。
或者忘记做 verify(test_inputs[i]) 而不是 verify(i).

解决这个问题，它会产生正确的结果：

function verify(text) {
  const stack = [];
  for (const c of text) {
    if (c === '(') stack.unshift(')')
    else if (c === '[') stack.unshift(']')
    else if (c === '<') stack.unshift('>')
    else if (c === stack[0]) stack.shift()
    else if (c === ')' || c === ']' || c === '>') return 0
  }
  return 1
}


const test_inputs = [
    "---(++++)----",
    "",
    "before ( middle []) after ",
    ") (",
    "<( >)",
    "( [ <> () ] <> )",
    " ( [)"
]
for (const s of test_inputs) {
  console.log(verify(s), s)
}

如何验证所有匹配的括号

How to verify all matching Brackets

javascript

arrays

parentheses