本文探讨了使用自定义栈检测括号字符串平衡性时常见的逻辑陷阱。通过分析一个初始实现中盲目弹出操作导致的问题，我们揭示了在处理栈数据结构时，循环条件设置的关键性。文章提供了一个修正后的解决方案，利用 `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() 次元素。这种“盲目弹出”的问题在于：
正确的逻辑应该是，只有当两个栈都有元素时才进行配对弹出操作，一旦其中一个栈为空，就应该停止弹出，然后检查两个栈的状态。
为了解决上述问题，我们需要修改弹出逻辑，使其在两个栈都非空的情况下才进行弹出操作。这可以通过一个 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 循环保证了：
将上述 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
}
}通过理解和应用这些原则，可以有效地避免在处理栈相关问题时常见的逻辑错误，并编写出更加稳定和正确的代码。
以上就是Java中基于自定义栈的括号平衡检测：问题分析与正确实现的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
广告Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
662
收藏
