JavaScript括号配对验证实现正确性咨询及优化方案寻求

现有实现问题分析 #

你的实现思路存在非常多核心错误，完全无法满足需求，典型问题如下：

• 首个逻辑完全不符合需求：你判断字符串首尾如果是数字/字母就直接返回无效，但比如a(b)c这类括号配对正常的字符串是合法的，你的逻辑会直接误判为无效。
• 存在大量低级笔误：遇到方括号[、圆括号(时你都在给opencurly（花括号计数）累加，还重复写了两个判断poppedItem == '['的分支，完全漏掉了闭方括号]的判断逻辑，各类括号的计数根本统计不准。
• 缺失核心的顺序校验逻辑：你同时用了计数和栈，但完全没用到栈的能力来校验括号嵌套顺序，比如([)]这类括号数量相等但顺序错误的非法输入，你的计数判断会误判为合法。
• 遍历逻辑混乱：你从后往前遍历的同时还在pop修改原数组，数组长度动态变化，循环的索引值根本匹配不到当前处理的元素，遍历逻辑完全错误。

更优解决方案 #

括号匹配的标准最优解法是栈+映射表，时间复杂度O(n)，空间复杂度O(n)，思路非常清晰：

1. 建立闭合括号到对应开括号的映射表，以及开括号的集合
2. 遍历字符串的每个字符：
   • 如果是开括号，直接压入栈
   • 如果是闭合括号：
     • 此时栈为空的话说明没有对应的开括号，直接返回无效
     • 弹出栈顶元素，如果和当前闭合括号对应的开括号不一致，说明嵌套顺序错误，直接返回无效
   • 如果是数字、字母，直接跳过不处理
3. 遍历结束后栈为空则所有括号都正确匹配，返回有效，否则还有未匹配的开括号，返回无效

优化后代码实现 #

function checkValidity(input) {
    const bracketMap = { ')': '(', ']': '[', '}': '{' };
    const openBrackets = new Set(['(', '[', '{']);
    const stack = [];
    for (const char of input) {
        if (openBrackets.has(char)) {
            stack.push(char);
        } else if (bracketMap[char]) {
            if (!stack.length || stack.pop() !== bracketMap[char]) {
                return 'Invalid';
            }
        }
        // 数字、字母直接跳过不处理
    }
    return stack.length === 0 ? 'Valid' : 'Invalid';
}

// 测试用例
console.log(checkValidity("{(([{cake}]icing))}")); // Valid
console.log(checkValidity("()(blue)(pink[)]{}")); // Invalid
console.log(checkValidity("([)]")); // Invalid
console.log(checkValidity("a(b)c123")); // Valid

内容的提问来源于stack exchange，提问作者aman aditya