本文探讨了在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 的逻辑是正确的。然而，随后的弹出逻辑存在一个关键问题：
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
，这样可以限制栈只能存储特定类型的数据。然而，由于本例有“不允许导入任何东西”的限制，故保持了 Object 类型。 - 代码可读性： 尽管功能受限，但通过清晰的变量命名和适当的注释，可以大大提高代码的可读性和可维护性。
通过理解并修正弹出逻辑，我们成功地在给定限制下，实现了对表达式平衡性的准确判断。
