Java中基于自定义栈的括号平衡检测：问题分析与正确实现-java教程-PHP中文网

java中基于自定义栈的括号平衡检测：问题分析与正确实现

本文探讨了使用自定义栈检测括号字符串平衡性时常见的逻辑陷阱。通过分析一个初始实现中盲目弹出操作导致的问题，我们揭示了在处理栈数据结构时，循环条件设置的关键性。文章提供了一个修正后的解决方案，利用 `while` 循环确保只有在两个栈都包含元素时才进行弹出操作，从而实现对括号数量平衡的准确判断，并附带了完整的自定义栈和节点实现代码。

理解括号平衡与自定义栈

括号平衡是编程中一个经典问题，通常用于检查表达式的语法正确性。一个简单的括号平衡定义是：字符串中开括号 ( 的数量必须等于闭括号 ) 的数量。在此教程中，我们将遵循一个特定的双栈策略来检测这种“数量平衡”：将所有开括号压入一个栈，所有闭括号压入另一个栈，然后尝试同时弹出，如果最终两个栈都为空，则认为数量上是平衡的。

为了实现这一目标，我们需要自定义栈数据结构。以下是基于链表实现的 Node 和 Stack 类：

// Node 类：栈中每个元素的载体
public class Node {
    Object info; // 存储元素信息
    Node next;   // 指向下一个节点

    Node(Object info, Node next){
        this.info = info;
        this.next = next;
    }
}

// Stack 类：基于链表实现的栈
public class Stack {
    private Node top; // 栈顶指针

    public Stack() {
        top = null; // 初始化时栈为空
    }

    // 检查栈是否为空
    public boolean isEmpty(){
        return (top == null);
    }

    // 元素入栈
    public void push(Object newItem){
        top = new Node(newItem, top); // 新元素成为栈顶，指向原来的栈顶
    }

    // 元素出栈
    public Object pop(){
        if (isEmpty()){
            System.out.println("Trying to pop when stack is empty"); // 尝试从空栈弹出时的警告
            return null;
        } else {
            Node temp = top; // 暂存当前栈顶
            top = top.next;  // 栈顶下移
            return temp.info; // 返回原栈顶元素
        }
    }

    // 清空栈
    void popAll(){
        top = null;
    }

    // 查看栈顶元素但不弹出
    public Object peek(){
        if (isEmpty()){
           System.out.println("Trying to peek when stack is empty");
           return null;
        } else {
           return top.info;
        }
    }
}

登录后复制

原始实现中的问题分析

在尝试检测括号平衡时，一个常见的错误是未能正确处理栈的弹出逻辑。考虑以下 isBalanced 方法的初始实现：

立即学习“Java免费学习笔记（深入）”；

static boolean isBalanced(String expr){
    // 基本情况：表达式为空或长度为奇数，则不平衡
    if (expr == null || expr.length() % 2 == 1) {
        return false;
    }

    Stack stack1 = new Stack(); // 存储开括号
    Stack stack2 = new Stack(); // 存储闭括号

    // 遍历表达式，将开括号和闭括号分别压入不同的栈
    for (int i = 0; i < expr.length(); i++){
        if (expr.charAt(i) == '(') {
            stack1.push(expr.charAt(i));
        }
        if (expr.charAt(i) == ')') {
           stack2.push(expr.charAt(i));
        }
    }

    // 尝试弹出所有元素
    for(int i = 0; i < expr.length(); i++) {
        stack1.pop(); // 盲目弹出
        stack2.pop(); // 盲目弹出
    }

    // 判断两个栈是否都为空
    return (stack1.isEmpty() && stack2.isEmpty()) ;
}

登录后复制

这个实现的主要问题在于第二个 for 循环：for(int i = 0; i < expr.length(); i++) { stack1.pop(); stack2.pop(); }。它尝试从 stack1 和 stack2 中各弹出 expr.length() 次元素。这种“盲目弹出”的问题在于：

知我AI

一款多端AI知识助理，通过一键生成播客/视频/文档/网页文章摘要、思维导图，提高个人知识获取效率；自动存储知识，通过与知识库聊天，提高知识利用效率。

101

查看详情

可能导致空栈弹出错误： 如果表达式中开括号或闭括号的数量少于 expr.length()，那么在循环执行到一定次数后，其中一个或两个栈就会变空，此时继续调用 pop() 将触发 isEmpty() 判断，并输出 Trying to pop when stack is empty 警告。
无法正确判断平衡性： 即使所有括号都被正确压入栈中，如果开括号和闭括号的数量不匹配，这个循环仍然会尝试弹出 expr.length() 次。最终，即使一个栈已经为空，另一个栈可能还有元素，或者两个栈都因为过度弹出而为空，导致返回结果不准确。例如，对于输入 ((，stack1 会有两个 (，stack2 为空。在第二个循环中，stack2.pop() 会立即报错，但如果忽略报错，循环会继续，最终 stack1 也可能被清空，导致误判为平衡。

正确的逻辑应该是，只有当两个栈都有元素时才进行配对弹出操作，一旦其中一个栈为空，就应该停止弹出，然后检查两个栈的状态。

修正后的括号平衡检测逻辑

为了解决上述问题，我们需要修改弹出逻辑，使其在两个栈都非空的情况下才进行弹出操作。这可以通过一个 while 循环来实现。

static boolean isBalanced(String expr){
    // 基本情况：表达式为空或长度为奇数，则不平衡
    if (expr == null || expr.length() % 2 == 1) {
        return false;
    }

    Stack stack1 = new Stack(); // 存储开括号
    Stack stack2 = new Stack(); // 存储闭括号

    // 遍历表达式，将开括号和闭括号分别压入不同的栈
    for (int i = 0; i < expr.length(); i++){
        if (expr.charAt(i) == '(') {
            stack1.push(expr.charAt(i));
        }
        if (expr.charAt(i) == ')') {
           stack2.push(expr.charAt(i));
        }
    }

    // 修正后的弹出逻辑：只有当两个栈都非空时才进行弹出
    while (!stack1.isEmpty() && !stack2.isEmpty()) {
        stack1.pop(); // 弹出 stack1 的一个元素
        stack2.pop(); // 弹出 stack2 的一个元素
    }

    // 此时，如果表达式是平衡的（即开括号和闭括号数量相等），
    // 那么两个栈应该同时变为空
    return (stack1.isEmpty() && stack2.isEmpty());
}

登录后复制

这个修正后的 while 循环保证了：

只要 stack1 和 stack2 都有元素，就尝试各弹出一个，模拟开括号与闭括号的“抵消”。
一旦其中一个栈变为空（意味着开括号或闭括号的数量用尽），循环立即停止。
最终，我们只需检查两个栈是否都为空。如果都为空，则说明开括号和闭括号的数量是相等的，表达式在数量上是平衡的。如果其中一个栈仍有元素，则说明数量不匹配，表达式不平衡。

完整代码示例

将上述 Node、Stack 和修正后的 isBalanced 方法整合，并添加一个 main 方法进行测试，可以得到一个完整的解决方案：

public class BalanceChecker {

    // Node 类：栈中每个元素的载体
    public static class Node {
        Object info;
        Node next;

        Node(Object info, Node next){
            this.info = info;
            this.next = next;
        }
    }

    // Stack 类：基于链表实现的栈
    public static class Stack {
        private Node top;

        public Stack() {
            top = null;
        }

        public boolean isEmpty(){
            return (top == null);
        }

        public void push(Object newItem){
            top = new Node(newItem, top);
        }

        public Object pop(){
            if (isEmpty()){
                System.out.println("Trying to pop when stack is empty");
                return null;
            } else {
                Node temp = top;
                top = top.next;
                return temp.info;
            }
        }

        void popAll(){
            top = null;
        }

        public Object peek(){
            if (isEmpty()){
               System.out.println("Trying to peek when stack is empty");
               return null;
            } else {
               return top.info;
            }
        }
    }

    // 修正后的括号平衡检测方法
    static boolean isBalanced(String expr){
        // 基本情况：表达式为空或长度为奇数，则不平衡
        if (expr == null || expr.length() % 2 == 1) {
            return false;
        }

        Stack stack1 = new Stack(); // 存储开括号
        Stack stack2 = new Stack(); // 存储闭括号

        // 遍历表达式，将开括号和闭括号分别压入不同的栈
        for (int i = 0; i < expr.length(); i++){
            if (expr.charAt(i) == '(') {
                stack1.push(expr.charAt(i));
            } else if (expr.charAt(i) == ')') { // 使用 else if 确保字符只处理一次
               stack2.push(expr.charAt(i));
            }
        }

        // 只有当两个栈都非空时才进行弹出
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            stack1.pop();
            stack2.pop();
        }

        // 判断两个栈是否都为空
        return (stack1.isEmpty() && stack2.isEmpty());
    }

    public static void main(String[] args) {
        // 测试用例
        String expr1 = "((()))"; // 期望：true
        String expr2 = "()()";   // 期望：true
        String expr3 = "(()";    // 期望：false (stack1 非空)
        String expr4 = "())";    // 期望：false (stack2 非空)
        String expr5 = ")((";    // 期望：false (stack1 非空, 尽管数量上平衡) - 注意：此方法只检查数量平衡，不检查顺序
        String expr6 = "";       // 期望：false (长度为0，按规则返回false)
        String expr7 = null;     // 期望：false (null，按规则返回false)
        String expr8 = "()(()";  // 期望：false (长度为奇数)

        System.out.println("Expression \"" + expr1 + "\" is balanced: " + isBalanced(expr1));
        System.out.println("Expression \"" + expr2 + "\" is balanced: " + isBalanced(expr2));
        System.out.println("Expression \"" + expr3 + "\" is balanced: " + isBalanced(expr3));
        System.out.println("Expression \"" + expr4 + "\" is balanced: " + isBalanced(expr4));
        System.out.println("Expression \"" + expr5 + "\" is balanced: " + isBalanced(expr5));
        System.out.println("Expression \"" + expr6 + "\" is balanced: " + isBalanced(expr6));
        System.out.println("Expression \"" + expr7 + "\" is balanced: " + isBalanced(expr7));
        System.out.println("Expression \"" + expr8 + "\" is balanced: " + isBalanced(expr8));

        // 示例输出：
        // Expression "((()))" is balanced: true
        // Expression "()()" is balanced: true
        // Expression "(()" is balanced: false
        // Expression "())" is balanced: false
        // Expression ")(((" is balanced: false
        // Expression "" is balanced: false
        // Expression "null" is balanced: false
        // Expression "()(()" is balanced: false
    }
}

登录后复制

注意事项与最佳实践

循环条件的重要性： 在处理栈或队列等数据结构时，务必仔细设计循环条件。盲目地根据字符串长度进行循环操作（如原始 for 循环）是常见的错误来源，因为它没有考虑数据结构自身的当前状态（如是否为空）。
明确“平衡”的定义： 本教程中的双栈方法主要检测的是开括号和闭括号的“数量平衡”。这意味着像 )( 这样的字符串，如果仅考虑数量，最终两个栈可能都为空（如果 ( 和 ) 的数量相等），但它在结构上是不平衡的。对于更严格的“结构平衡”（即括号必须正确嵌套），通常会采用单栈方法：遇到开括号压栈，遇到闭括号则尝试从栈顶弹出一个开括号进行匹配，如果栈为空或不匹配则不平衡，最终栈为空则平衡。
错误处理与调试： 当遇到类似 Trying to pop when stack is empty 的运行时错误时，这通常意味着你在不应该弹出的时候尝试弹出了。这提示你需要检查 pop 操作前的 isEmpty() 条件，或调整循环逻辑以避免这种情况。
代码复用与标准库： 在实际开发中，如果允许，通常会优先使用Java标准库中提供的 java.util.Stack 或 java.util.Deque（推荐作为栈使用），因为它们经过了充分测试和优化，且代码更简洁。自定义栈通常用于学习目的或有特殊性能/功能需求时。
健壮性考虑： 在 isBalanced 方法的开头，我们加入了对 null 字符串和长度为奇数字符串的快速判断，这提高了方法的健壮性。