本文针对使用自定义栈实现括号平衡检测时常见的逻辑错误进行深入分析与修复。文章详细阐述了原始代码在弹出操作中因循环条件不当导致的问题，并提供了一种基于`while`循环的改进方案，确保了栈操作的正确性及平衡性判断的准确性，同时兼容了在不导入任何库的限制下使用自定义栈的场景。
引言：括号平衡检测及其挑战
括号平衡检测是计算机科学中一个经典的算法问题，广泛应用于编译器、代码编辑器等领域，用于验证表达式或代码块的语法正确性。其核心思想是确保每个开括号（如 (, [, {）都有一个对应的闭括号（如 ), ], }），并且它们的嵌套顺序是正确的。栈（Stack）作为一种“后进先出”（LIFO）的数据结构，天然适合解决这类问题。
在某些特定场景下，我们可能被要求使用自定义的栈实现，而非Java标准库中的 java.util.Stack。这通常发生在教学环境或对内存、性能有极致要求的嵌入式系统中。在这种情况下，开发者需要自行实现 node 类来构建链式栈。
问题分析：自定义栈的错误使用
原始代码尝试通过两个自定义栈来检测括号平衡。其基本思路是将所有开括号 ( 压入 stack1，将所有闭括号 ) 压入 stack2。随后，计划通过一个循环将两个栈中的元素逐一弹出，如果最终两个栈都为空，则认为表达式是平衡的。
以下是原始 isBalanced 方法的关键部分：
立即学习“Java免费学习笔记（深入）”；
static boolean isBalanced(String expr){ // base case: Length of the expression must be even if (expr == NULL || expr.length() % 2 == 1) { return false; } Stack stack1 = new Stack(); Stack stack2 = new Stack(); // traverse the input expression and push characters 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)); } } // Problematic popping loop for(int i = 0; i< expr.length(); i++) { stack1.pop(); // May cause issues if stack1 is empty stack2.pop(); // May cause issues if stack2 is empty } return (stack1.isEmpty() && stack2.isEmpty()) ; }
错误根源：不当的弹出循环条件
上述代码中的第二个 for 循环是导致问题的主要原因：
for(int i = 0; i< expr.length(); i++) { stack1.pop(); stack2.pop(); }
这个循环的迭代次数是 expr.length()，即表达式的总长度。然而，stack1 和 stack2 中实际存储的元素数量通常远小于 expr.length()，它们只分别存储了开括号和闭括号。例如，对于输入 ((()))，expr.length() 为 6。stack1 和 stack2 各自只包含 3 个元素。当 for 循环执行到第四次迭代时，stack1 和 stack2 都已经为空，但循环仍会继续尝试调用 pop() 方法。由于自定义 Stack 类中的 pop() 方法在栈为空时会打印 “Trying to pop when stack is empty” 并返回 null，这就会导致控制台输出多条错误信息。
尽管最终 stack1.isEmpty() && stack2.isEmpty() 可能会返回 true（因为它们确实被清空了），但这并非通过正确的逻辑实现的，并且伴随着不必要的错误提示。这种方法实际上只是检查了开括号和闭括号的数量是否相等，而不是严格意义上的结构平衡（即 ( 必须在其对应的 ) 之前出现）。但考虑到原始代码的设计意图和问题描述，我们主要关注如何修正其弹出逻辑以实现其特定的“平衡”定义。
解决方案：基于while循环的精确弹出
为了正确地从两个栈中弹出元素，我们应该在两个栈都还有元素时才进行弹出操作。一旦其中任何一个栈变空，就应该停止弹出，因为这意味着其中一类括号已经用尽。
修正后的 isBalanced 方法如下所示：
public class BalancedParenthesesChecker { // Stack class (provided by user, for context) static class Node { Object info; Node next; Node(Object info, Node next){ this.info=info; this.next=next; } } 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; } } } /** * 检查给定表达式中的括号是否“平衡”。 * 此方法根据原始问题对“平衡”的定义进行修复： * 仅检查开括号 '(' 的数量是否与闭括号 ')' 的数量相等。 * 它不检查括号的嵌套顺序。 * * @param expr 待检查的字符串表达式。 * @return 如果开括号和闭括号数量相等且表达式长度为偶数，则返回 true；否则返回 false。 */ 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()) ; } public static void main(String[] args) { System.out.println("Testing ((())): " + isBalanced("((()))")); // Expected: true System.out.println("Testing ()): " + isBalanced("(())")); // Expected: true System.out.println("Testing )(: " + isBalanced(")(")); // Expected: true (based on this specific definition) System.out.println("Testing (: " + isBalanced("(")); // Expected: false (odd length) System.out.println("Testing ): " + isBalanced(")")); // Expected: false (odd length) System.out.println("Testing (()): " + isBalanced("(()")); // Expected: false (odd length) System.out.println("Testing empty string: " + isBalanced("")); // Expected: true (length 0, both stacks empty) } }
改进逻辑说明：
- 收集括号： 第一个 for 循环保持不变，它负责将表达式中的所有开括号 ( 压入 stack1，所有闭括号 ) 压入 stack2。
- 精确弹出： 关键的改变在于第二个循环。我们使用 while (!stack1.isEmpty() && !stack2.isEmpty()) 作为循环条件。这意味着只有当 stack1 和 stack2 都包含元素时，循环才会继续执行。每次迭代，两个栈各弹出一个元素。
- 避免空栈操作： 一旦其中一个栈变为空，循环就会终止。这有效地避免了在空栈上调用 pop() 方法，从而消除了 Trying to pop when stack is empty 的错误输出。
- 最终判断： 循环结束后，如果 stack1 和 stack2 都为空，则说明开括号和闭括号的数量是相等的，返回 true。否则，如果其中一个栈仍有剩余元素（表示数量不匹配），则返回 false。
自定义栈与节点类概览
为了完整性，这里再次展示自定义的 Stack 和 Node 类的结构。它们是实现上述逻辑的基础，且严格遵循了不导入任何标准库的限制。
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; // 返回栈顶元素，不移除 } } }
这些自定义类提供了栈的基本功能，并且在 pop 和 peek 方法中包含了对空栈操作的错误提示，这对于调试非常有帮助。
注意事项与最佳实践
- 明确“平衡”定义： 本教程所修复的 isBalanced 方法，其“平衡”的定义是：表达式中开括号 ( 的数量与闭括号 ) 的数量相等，且表达式总长度为偶数。它不检查括号的嵌套顺序。例如，)( 在此定义下会被认为是平衡的（因为一个 ( 和一个 ) 数量相等）。如果需要实现严格的结构平衡检测（例如 ([{}]) 应该平衡，而 ([)] 不平衡），通常会采用单栈匹配法：遇到开括号压栈，遇到闭括号则检查栈顶是否为对应的开括号并弹出，最终栈为空则平衡。
- 栈操作的边界条件： 在进行 pop() 或 peek() 操作之前，始终应该检查栈是否为空 (isEmpty())。这是避免运行时错误的关键。自定义栈的 pop 方法中已经包含了此检查，并提供了友好的错误信息。
- 循环条件的精确性： 避免使用固定次数的循环来处理动态数据结构（如栈）的元素。应根据数据结构的实际状态（如 !isEmpty()）来控制循环，确保操作的合法性。
- 代码可读性： 良好的变量命名（如 stack1 和 stack2）和注释有助于理解代码的意图和逻辑。
总结
通过对 isBalanced 方法中弹出循环逻辑的修正，我们成功解决了自定义栈在处理括号平衡问题时出现的 Trying to pop when stack is empty 错误。核心改进在于将固定次数的 for 循环替换为基于栈实际状态的 while 循环，确保了只有在栈非空时才执行弹出操作。这个案例强调了在操作数据结构时，精确控制循环条件和处理边界情况的重要性，尤其是在使用自定义数据结构且无法依赖标准库的健壮性时。理解并正确应用这些原则，是编写高质量、健壮代码的基础。
评论（已关闭）
评论已关闭