Java自定义链表栈实现括号匹配教程

## Java自定义链表栈实现括号匹配检查指南 本文深入探讨了如何利用Java自定义链表栈实现高效的括号匹配检查。针对传统双栈法无法有效处理嵌套顺序的弊端，详细阐述了业界广泛应用的单栈算法原理及其Java代码实现。**文章首先分析了括号平衡性的重要性，随后通过实例代码展示了如何使用自定义栈结构，包括`Node`节点类和`Stack`栈类，来实现对包含圆括号`()`的表达式进行平衡性校验。** 读者将通过本文掌握栈数据结构在解决结构匹配问题中的核心应用，最终能够构建出健壮且高效的括号平衡性检查逻辑，为编译器、代码分析等应用奠定基础。教程还包含了详细的测试用例，确保读者能够充分理解并应用所学知识。

本教程深入探讨了如何利用自定义实现的链表栈来高效、准确地判断括号表达式的平衡性。文章首先剖析了传统两栈方法的不足，随后详细阐述了业界普遍采用的单栈算法原理，并提供了完整的Java代码实现及使用示例。通过本指南，读者将掌握栈在解决结构匹配问题中的核心应用，并能构建健壮的括号平衡性检查逻辑。

引言：括号平衡性与栈的重要性

在计算机科学中，括号平衡性是一个基础而重要的问题，常见于编译器、解释器和代码分析工具中。一个括号表达式被认为是平衡的，当且仅当它满足以下条件：

1. 表达式中每个开括号（如 (）都有一个对应的闭括号（如 )）。
2. 括号的嵌套顺序是正确的，即任何一个闭括号都必须与其最近的未闭合的开括号相匹配。

例如，((())) 和 () 是平衡的，而 (()、)( 和 ()) 则是不平衡的。栈（Stack）作为一种“后进先出”（LIFO）的数据结构，天然适用于解决这类需要匹配和回溯的问题。

问题剖析：两栈法的局限性

在最初的尝试中，可能有人会想到使用两个栈来解决括号平衡问题：一个栈用于存储开括号，另一个栈用于存储闭括号。然后，通过比较两个栈中元素的数量来判断是否平衡。然而，这种方法存在根本性的缺陷。

考虑以下原始代码片段中的 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));
        }
    }
    // 尝试弹出所有元素
    for(int i = 0; i< expr.length(); i++) {
      stack1.pop();
      stack2.pop();
    }
    return (stack1.isEmpty() && stack2.isEmpty()) ;
}

这种方法的缺点主要体现在：

1. 无法检查嵌套顺序：它只能保证开括号和闭括号的数量相等，但无法判断它们的出现顺序是否正确。例如，对于表达式 )(，stack1 会包含 (，stack2 会包含 )。最终两者都为空，但 )( 显然是不平衡的。
2. 不必要的弹出操作：第二个 for 循环尝试无差别地弹出 expr.length() 次元素。这可能导致在栈中元素不足时，反复调用 pop() 方法，从而触发“Trying to pop when stack is empty”的错误提示，即使最终结果可能碰巧是 true 或 false，也掩盖了潜在的逻辑错误。正确的做法应该是在弹出前检查栈是否为空，并且弹出的次数应该与栈中实际的元素数量相关，而非表达式的总长度。

因此，这种两栈分离、独立计数的策略并不能有效地解决括号平衡性问题。我们需要一种能够实时匹配括号的机制。

核心算法：单栈法实现括号平衡性检查

解决括号平衡问题的标准方法是使用一个单一的栈。其核心思想是：当遇到开括号时，将其压入栈中；当遇到闭括号时，检查栈顶元素是否为对应的开括号。

以下是单栈算法的详细步骤：

1. 预处理与边界条件检查：

   • 如果表达式为 null 或其长度为奇数，则直接判断为不平衡（因为平衡的括号表达式长度必须为偶数）。
   • 如果表达式为空字符串 ""，通常认为它是平衡的。

2. 遍历表达式：从左到右逐个字符地扫描输入表达式。

3. 处理开括号：如果当前字符是一个开括号（如 (），则将其压入栈中。

4. 处理闭括号：如果当前字符是一个闭括号（如 )）：

   • 检查栈是否为空：如果此时栈为空，说明没有对应的开括号可供匹配，因此表达式不平衡，立即返回 false。
   • 弹出并匹配：如果栈不为空，则从栈中弹出一个元素。这个弹出的元素应该是一个开括号，并且必须与当前遇到的闭括号类型相匹配。对于本例中只有 () 一种括号的情况，弹出的必须是 (。如果弹出的不是 (，则表示括号不匹配，表达式不平衡，立即返回 false。

5. 最终检查：在遍历完整个表达式后：

   • 如果栈为空，表示所有开括号都找到了对应的闭括号并成功匹配，表达式是平衡的。
   • 如果栈不为空，表示仍有未匹配的开括号（即多余的开括号），表达式不平衡。

根据上述算法，我们可以重构 isBalanced 方法，并结合自定义的 Stack 类实现：

public class BalanceChecker {

    // 假设 Stack 和 Node 类已在同一包中定义，且不允许导入其他库

    /**
     * 检查给定字符串表达式中的括号是否平衡。
     * 仅支持圆括号 ()。
     *
     * @param expr 待检查的字符串表达式。
     * @return 如果括号平衡则返回 true，否则返回 false。
     */
    static boolean isBalanced(String expr) {
        // 初始检查：null或奇数长度的表达式必然不平衡
        if (expr == null || expr.length() % 2 != 0) {
            return false;
        }
        // 对于空字符串，通常认为是平衡的
        if (expr.isEmpty()) {
            return true;
        }

        Stack stack = new Stack(); // 使用单个栈

        // 遍历输入表达式
        for (int i = 0; i < expr.length(); i++) {
            char current = expr.charAt(i);

            // 如果是开括号，则压入栈中
            if (current == '(') {
                stack.push(current);
            }
            // 如果是闭括号
            else if (current == ')') {
                // 如果栈为空，说明没有匹配的开括号，不平衡
                if (stack.isEmpty()) {
                    return false;
                }
                // 弹出栈顶元素，检查是否匹配
                // pop() 方法返回 Object，需要强制转换为 char
                char topChar = (char) stack.pop();
                // 对于只有一种括号的情况，这一步的匹配检查是隐式的
                // 因为我们只压入 '('，所以如果弹出不是 '('，说明逻辑有问题
                // 但为了通用性，保留此检查
                if (topChar != '(') {
                    return false; // 弹出的不是对应的开括号，则不平衡
                }
            }
            // 假设表达式只包含括号，如果遇到其他字符，可以根据需求处理
            // 例如，可以忽略，或者直接返回 false (视为无效字符)
        }

        // 遍历结束后，如果栈为空，则所有开括号都有匹配的闭括号，表达式平衡
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println("测试用例:");
        System.out.println("((())) is balanced: " + isBalanced("((()))")); // true
        System.out.println("() is balanced: " + isBalanced("()"));         // true
        System.out.println("(() is balanced: " + isBalanced("(()"));       // false (多余的开括号)
        System.out.println(")() is balanced: " + isBalanced(")()"));       // false (开局闭括号)
        System.out.println(")( is balanced: " + isBalanced(")("));         // false (顺序错误)
        System.out.println("'' is balanced: " + isBalanced(""));           // true (空字符串)
        System.out.println("null is balanced: " + isBalanced(null));       // false (null字符串)
        System.out.println("(( is balanced: " + isBalanced("(("));         // false (多余的开括号)
        System.out.println(")) is balanced: " + isBalanced("))"));         // false (多余的闭括号)
        System.out.println("())(() is balanced: " + isBalanced("())(()")); // false (复杂不平衡)
    }
}

自定义栈与节点类的实现

由于题目要求不允许导入任何库，我们需要使用自定义的 Stack 和 Node 类。这些类通常通过链表结构实现，以提供动态大小的栈。

Node 类

Node 类是链表的基本组成单元，每个节点包含数据 (info) 和指向下一个节点的引用 (next)。

public class Node {
    Object info; // 存储节点信息
    Node next;   // 指向链表中的下一个节点

    /**
     * 构造函数，创建一个新的节点。
     * @param info 节点中存储的数据。
     * @param next 指向下一个节点的引用。
     */
    Node(Object info, Node next){
        this.info = info;
        this.next = next;
    }
}

Stack 类

Stack 类基于 Node 类实现了一个链表结构的栈，遵循 LIFO（Last-In, First-Out）原则。栈的顶部由 top 引用指示。

public class Stack {
    private Node top; // 栈顶元素的引用

    /**
     * 构造函数，创建一个空栈。
     */
    public Stack() {
        top = null;
    }

    /**
     * 检查栈是否为空。
     * @return 如果栈为空则返回 true，否则返回 false。
     */
    public boolean isEmpty(){
        return (top == null);
    }

    /**
     * 将一个新元素压入栈顶。
     * @param newItem 要压入栈的元素。
     */
    public void push(Object newItem){
        top = new Node(newItem, top); // 新元素成为新的栈顶，并指向原来的栈顶
    }

    /**
     * 从栈顶弹出一个元素。
     * @return 栈顶元素。如果栈为空，则打印错误信息并返回 null。
     */
    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;
    }

    /**
     * 查看栈顶元素但不将其移除。
     * @return 栈顶元素。如果栈为空，则打印错误信息并返回 null。
     */
    public Object peek(){
        if (isEmpty()){
           System.out.println("Trying to peek when stack is empty");
           return null;
        } else {
           return top.info; // 返回栈顶元素的数据
        }
    }
} // End of Stack using a linked list

示例与注意事项

示例测试

为了验证 isBalanced 方法的正确性，我们可以使用 main 方法进行测试：

// 包含在 BalanceChecker 类中的 main 方法
public static void main(String[] args) {
    System.out.println("测试用例:");
    System.out.println("((())) is balanced: " + isBalanced("((()))")); // true
    System.out.println("() is balanced: " + isBalanced("()"));         // true
    System.out.println("(() is balanced: " + isBalanced("(()"));       // false (多余的开括号)
    System.out.println(")() is balanced: " + isBalanced(")()"));       // false (开局闭括号)
    System.out.println(")( is balanced: " + isBalanced(")("));         // false (顺序错误)
    System.out.println("'' is balanced: " + isBalanced(""));           // true (空字符串)
    System.out.println("null is balanced: " + isBalanced(null));       // false (null字符串)
    System.out.println("(( is balanced: " + isBalanced("(("));         // false (多余的开括号)
    System.out.println(")) is balanced: " + isBalanced("))"));         // false (多余的闭括号)
    System.out.println("())(() is balanced: " + isBalanced("())(()")); // false (复杂不平衡)
}

注意事项

1. 无导入限制：严格遵守不允许导入任何Java标准库的限制，所有数据结构（如栈）都必须是自定义实现。
2. 类型转换：Stack 类的 push 和 pop 方法处理的是 Object 类型。在 isBalanced 方法中，当从栈中弹出字符时，需要进行显式的 (char) stack.pop() 类型转换。
3. 扩展性：当前 isBalanced 方法仅支持圆括号 ()。如果需要支持多种括号类型（如 {}, []），则需要在 if-else if 结构中增加对这些括号的判断，并在弹出时确保匹配的是正确的开括号。例如，遇到 ] 时，栈顶必须是 [。
4. 错误处理：自定义 Stack 的 pop() 和 peek() 方法在栈为空时会打印错误信息并返回 null。在 isBalanced 方法中，我们通过 stack.isEmpty() 提前检查来避免这种情况，这是更健壮的做法。
5. 效率：单栈算法的时间复杂度为 O(n)，其中 n 是表达式的长度，因为它只需要对表达式进行一次遍历。空间复杂度为 O(n)，最坏情况下（所有字符都是开括号）栈会存储所有开括号。

总结

本教程详细阐述了使用自定义链表栈来检查括号表达式平衡性的正确方法。通过对比分析两栈法的局限性，我们强调了单栈算法在处理括号嵌套和匹配方面的优越性。掌握这种利用栈解决结构匹配问题的能力，对于理解和编写更复杂的解析器和验证逻辑至关重要。遵循本指南提供的代码示例和注意事项，开发者可以构建出高效、健壮的括号平衡性检查机制。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~