Java Program to Determine Whether a Given String of Parentheses (Single Type) is Properly Nested

正确嵌套括号是计算机科学中的一个常见问题，特别是在数学方程、解释器和编译器中。如果保留适当的开括号和闭括号的顺序，一组括号就被认为是“正确嵌套”的。

问题陈述

给定一个只包含 ( 和 ) 字符的 字符串，任务是确定该字符串是否正确嵌套，条件是：

1. 每个开括号都有一个相同的闭括号。
2. 由于括号的排列是适当的，闭括号不能出现在开括号之前。

示例

• "()" 是正确嵌套的。
• "(())" 是正确嵌套的。
• "(()))" 不是正确嵌套的。
• "())(" 不是正确嵌套的。

方法 1 - 基于栈

我们可以应用基于栈的方法来确定一串括号是否正确嵌套。栈 数据结构 非常适合在遍历字符串时跟踪开括号，因为它遵循 后进先出 (LIFO) 原则。

算法

1. 初始化一个空栈。
2. 遍历字符串中的每个字符
   
   • 如果字符是开括号 (，则将其压入栈中。
   • 如果字符是闭括号 )，则检查栈
     
     • 如果栈为空，则表示没有对应的开括号，因此字符串不是正确嵌套的。
     • 如果栈不为空，则弹出栈顶元素（应为开括号）。
3. 遍历完整个字符串后，检查栈
   
   • 如果 栈 为空，则字符串嵌套正确。
   • 如果栈不为空，则表示有未匹配的开括号，因此字符串不是正确嵌套的。

文件名：ParenthesesNestingChecker.java

输出

 
Is the string "()" properly nested? true
Is the string "(())" properly nested? true
Is the string "(()))" properly nested? false
Is the string "())(" properly nested? false
Is the string "(()(()))" properly nested? True   

解释

栈：用于记录遇到的开括号。每次遇到开括号时，就将其压入栈中。遇到闭括号时，则查看栈顶。当弹出栈顶的开括号时，表示匹配成功。

遍历：逐个字符检查字符串。为了保持正确的嵌套，栈的操作（压栈和弹栈）确保每个闭括号都与一个开括号匹配。

最终检查：如果遍历完字符串后栈为空，则所有括号都已正确匹配，表明字符串嵌套正确。

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

方法 2 - 计数法

另一种判断括号字符串是否正确嵌套的方法是使用计数法，它比基于栈的方法更简单、更节省空间。该方法依赖于在遍历字符串时维护开括号 ( 和闭括号 ) 的平衡计数。

方法说明

此方法不使用栈，而是维护一个整数计数来跟踪开括号 ( 和闭括号 ) 之间的平衡。

1. 初始化计数为 0。
2. 逐个字符遍历字符串
   
   • 如果字符是开括号 (，则增加计数变量。
   • 如果字符是闭括号 )，则减少计数变量。
   • 如果在任何时候计数变量变为负数，则表示闭括号的数量多于开括号，并且字符串立即被认为不是正确嵌套的。
3. 遍历完成后，如果计数不为零，则表示有未匹配的开括号，字符串不是正确嵌套的。否则，字符串就是正确嵌套的。

输出

 
Properly Nested
Not Properly Nested   

结论

对于检测括号字符串是否正确嵌套，基于栈的方法和计数法都很有用，并且各有优点。对于表达式求值和语法验证等任务，基于栈的方法因其通用性和健壮性而不可或缺。它非常适合处理涉及嵌套或多种括号类型的复杂场景。

另一方面，计数法更直接、更节省空间，使其成为内存消耗是问题的单种括号问题的理想选择。对于简单的括号匹配，与具有更广泛应用范围的栈方法相比，计数法更快、更容易使用。

结合使用这些方法，您可以获得处理各种与嵌套结构相关的计算挑战所需的工具。