Java Bracket Balancing(括号匹配)代码对测试用例{(([])[])[]]}运行异常求助

问题排查结果 #

现有代码存在两个核心逻辑缺陷，直接导致测试用例{(([])[])[]]}运行异常：

• 遇到右括号时未先判断栈是否为空就直接调用stack.peek()：你提供的测试用例末尾多了1个额外的]，前面所有括号完成匹配后栈已经为空，此时调用peek()会直接抛出EmptyStackException，程序中断不会走到最终栈是否为空的判断逻辑。
• 缺少括号不匹配的异常分支：如果当前右括号和栈顶左括号类型不匹配（比如栈顶是(，当前字符是]），现有代码无任何处理逻辑，会直接跳过该字符继续遍历，最终结果完全错误。

修复后代码 #

package myProject;
import java.util.*;

public class bracketBalancing {
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter String");
        String s=sc.next();
        Stack<Character> stack=new Stack<Character>();
        boolean isBalanced = true;
        if(s.length()==0) {
            System.out.println("string is empty");
            sc.close();
            return;
        }
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch=='('||ch=='{'||ch=='['){
                stack.push(ch);
            }
            else if(ch==')'||ch=='}'||ch==']'){
                // 栈为空说明当前右括号没有对应的左括号，直接判定不匹配
                if(stack.isEmpty()){
                    isBalanced = false;
                    break;
                }
                char top = stack.peek();
                if((ch==')' && top=='(') || (ch=='}' && top=='{') || (ch==']' && top=='[')){
                    stack.pop();
                }else{
                    // 括号类型不匹配，直接标记失败
                    isBalanced = false;
                    break;
                }
            }
        }
        // 两个条件同时满足才是匹配：全程无类型不匹配、遍历结束后栈为空
        if(isBalanced && stack.empty()){
            System.out.println("YES");
        }else{
            System.out.println("No");
        }
        sc.close();
    }
}

内容的提问来源于stack exchange，提问作者shubham bhardwaj