Java中自定义栈实现与括号平衡性检查的优化-java教程-PHP中文网

Java中自定义栈实现与括号平衡性检查的优化

花韻仙語

发布： 2025-10-11 13:18:13

原创

194人浏览过

java中自定义栈实现与括号平衡性检查的优化

本文探讨了在Java中利用自定义栈实现括号平衡性检查时遇到的常见问题及解决方案。针对一种将开闭括号分别压入两个栈的特殊平衡性定义，详细分析了原始弹出逻辑的错误，并提供了一种基于`while`循环的优化方案，确保在不引入外部库的限制下，正确判断表达式的平衡性。

理解括号平衡性检查的特定需求

在处理字符串表达式的平衡性问题时，一种常见的策略是利用栈的LIFO（后进先出）特性。然而，本教程所讨论的场景采用了一种独特的平衡性定义：将表达式中的所有开括号（(）压入一个栈（stack1），将所有闭括号（)）压入另一个栈（stack2）。其核心逻辑是，如果最终两个栈都能被清空，则认为表达式是平衡的。这种方法与传统上使用单个栈进行匹配（即遇到开括号入栈，遇到闭括号则尝试出栈匹配）有所不同。

为了实现这一目标，我们首先需要自定义Stack和Node类，因为不允许导入任何外部库。

自定义节点类 Node

Node类是构成链式栈的基本单元，它包含数据（info）和指向下一个节点的引用（next）。

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

public class Node {
    Object info;
    Node next;

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

登录后复制

自定义栈类 Stack

Stack类基于链表实现，提供了基本的栈操作：isEmpty（判断是否为空）、push（入栈）、pop（出栈）、peek（查看栈顶元素）和popAll（清空栈）。

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 方法来检查表达式的平衡性。原始实现中，将开括号压入 stack1，闭括号压入 stack2 的逻辑是正确的。然而，随后的弹出逻辑存在一个关键问题：

稿定AI

拥有线稿上色优化、图片重绘、人物姿势检测、涂鸦完善等功能

查看详情

  static boolean isBalanced(String expr){
      // ... (省略初始化和压栈部分)

      for(int i = 0; i < expr.length(); i++) {
        stack1.pop(); // 尝试从 stack1 弹出一个元素
        stack2.pop(); // 尝试从 stack2 弹出一个元素
      }
      return (stack1.isEmpty() && stack2.isEmpty()); 
    }

登录后复制

这个 for 循环会无条件地执行 expr.length() 次 pop 操作。这意味着，即使其中一个栈已经为空，它也会尝试继续弹出元素，从而导致 Trying to pop when stack is empty 的错误信息大量出现。更重要的是，这种固定次数的弹出并不能准确反映两个栈是否“同步”清空，因为两个栈中的元素数量可能不相等，或者它们可能在不同的时间点变空。这种做法无法正确判断表达式是否按照其特定定义是平衡的。

优化弹出逻辑

为了解决上述问题，我们需要修改弹出逻辑，使其能够更智能地判断何时停止弹出，并最终检查两个栈是否都为空。根据这种双栈平衡性定义，正确的做法是：只要两个栈中都有元素，就同时从两个栈中弹出一个元素。一旦其中一个栈变为空，就停止弹出。最后，检查两个栈是否都为空。

以下是优化后的 isBalanced 方法：

class Solution { // 可以将 isBalanced 方法放在一个类中
    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();
            stack2.pop();
        }

        // 最终判断：如果两个栈都为空，则认为表达式平衡
        return (stack1.isEmpty() && stack2.isEmpty()); 
    }
}

登录后复制

解释：

初始检查： 表达式为 null 或长度为奇数时，不可能平衡，直接返回 false。
分离压栈： 遍历表达式，将所有 ( 压入 stack1，所有 ) 压入 stack2。
同步弹出： 使用 while (!stack1.isEmpty() && !stack2.isEmpty()) 循环。这个循环会持续执行，只要两个栈中都有元素，就分别从 stack1 和 stack2 中弹出一个元素。一旦其中一个栈变为空，循环就会终止。
最终判断： 循环结束后，如果 stack1 和 stack2 都为空，则说明所有开括号和闭括号都已成功“匹配”并弹出，表达式被认为是平衡的。如果其中任何一个栈不为空，则表示开括号或闭括号的数量不匹配，表达式不平衡。

通过这种方式，我们避免了在空栈上进行 pop 操作，并根据自定义的平衡性规则，更准确地判断了表达式的平衡状态。

注意事项与最佳实践

明确平衡性定义： 本教程遵循的是一种特殊的平衡性定义，即“开括号数量等于闭括号数量，且它们可以同步清空”。这与传统的“括号匹配”（例如 ([{}]) 是平衡的，([)] 不平衡）有所不同。在实际应用中，请务必明确所需的平衡性规则。对于更通用的括号匹配问题，通常使用单个栈，遇到开括号入栈，遇到闭括号时检查栈顶是否为对应的开括号并出栈。
错误处理： 自定义 Stack 类中的 pop() 和 peek() 方法包含了在栈为空时打印错误信息并返回 null 的逻辑。这是一种基本的错误处理方式，但在生产环境中，通常会选择抛出 EmptyStackException 或其他运行时异常，以便调用方能够更优雅地处理这些异常情况。
泛型使用： 自定义栈目前使用的是 Object 类型，这意味着它可以存储任何类型的对象。在Java中，为了提高类型安全性和代码可读性，强烈建议使用泛型来定义栈，例如 public class Stack<T>，这样可以限制栈只能存储特定类型的数据。然而，由于本例有“不允许导入任何东西”的限制，故保持了 Object 类型。
代码可读性： 尽管功能受限，但通过清晰的变量命名和适当的注释，可以大大提高代码的可读性和可维护性。

通过理解并修正弹出逻辑，我们成功地在给定限制下，实现了对表达式平衡性的准确判断。

以上就是Java中自定义栈实现与括号平衡性检查的优化的详细内容，更多请关注php中文网其它相关文章！