检查表达式中的括号是否平衡

引言

平衡括号在编程语言和数学表达式中起着至关重要的作用。它们确保语法正确，并且代码或表达式可以被无错误地解释。检查括号平衡性是编程中的一项常见任务。

理解平衡括号

在编程中，括号有不同的形式：圆括号 '()'、方括号 '[]' 和花括号 '{}'。如果每个开括号都有一个相应的闭括号，并且顺序正确，则表达式被认为是平衡括号。

例如

"(a + b)" 是平衡的。

"{[x + y] * z}" 是平衡的。

"((a + b)" 是不平衡的。

"{[x + y) * z}" 是不平衡的。

为什么平衡括号很重要

平衡括号对于维护编程语言中表达式的句法完整性至关重要。它们常用于数学表达式、条件语句、循环以及堆栈等各种数据结构中。带有不平衡括号的表达式可能导致语法错误、逻辑错误或意外的程序行为。因此，验证表达式中括号的平衡性至关重要。

例如，考虑表达式 if (x > 0 { print("Positive"); }。这里，if 语句中缺少右括号可能导致编译错误或导致程序执行不正确。

平衡括号的挑战

检查括号平衡性的任务涉及检查表达式并验证每个开括号是否具有相应且顺序正确的闭括号。必须考虑各种类型的括号，括号的嵌套增加了问题的复杂性。需要一个健壮的算法来有效地处理不同的情况并准确识别不平衡。

检查平衡括号的算法

为了检查表达式中括号的平衡性，我们可以使用堆栈数据结构。该算法涉及遍历表达式并将开括号压入堆栈。当遇到闭括号时，我们检查堆栈是否为空。如果不是，我们从堆栈中弹出顶部元素并将其与当前闭括号进行比较。如果它们匹配，则继续该过程。如果堆栈为空或括号不匹配，则表达式不平衡。

实施

说明

• areBracketsBalanced 函数接受一个字符串表达式作为参数，并返回一个布尔值，指示表达式中的括号是否平衡。
• 它初始化一个空堆栈（bracketStack），用于存储在遍历输入表达式字符时遇到的开括号。
• 程序使用 for 循环遍历表达式中的每个字符。
• 如果字符是开括号（'(', '{', 或 '['），则将其压入堆栈。
• 如果字符是闭括号（')', '}', 或 ']'），程序检查堆栈是否为空。如果为空，则表达式被认为是不平衡的，因为当前闭括号没有匹配的开括号。
• 如果堆栈不为空，程序从堆栈中检索顶部元素（遇到的最后一个开括号），并将其与当前闭括号进行比较。
• 如果它们不匹配，则表达式被认为是不平衡的。循环继续，直到表达式中的所有字符都已处理完毕。
• 循环结束后，程序检查堆栈是否为空。如果为空，则表达式被认为是平衡的，因为所有开括号都已与相应的闭括号匹配。
• 如果堆栈不为空，则表示存在不匹配的开括号，表达式被认为是不平衡的。
• 在 main 函数中，使用 std::cin 提示用户输入表达式。
• 然后使用输入的表达式调用 areBracketsBalanced 函数，程序根据结果输出表达式是平衡的还是不平衡的。

程序输出

时间复杂度和空间复杂度（使用堆栈）

时间复杂度

这种方法的时间复杂度也是 O(n)，其中 'n' 是输入表达式的长度。在最坏的情况下，表达式中的每个字符都被处理一次。压入和弹出堆栈以及比较都是常数时间操作。

空间复杂度

在最坏的情况下，空间复杂度为 O(n)。这是因为在最坏的情况下，所有开括号都可能在遇到闭括号之前被压入堆栈。因此，堆栈所需的空间与表达式中开括号的数量成正比。

另一种方法

另一种不使用堆栈检查平衡括号的方法是遍历表达式并使用计数器跟踪平衡。这种方法使用一个整数变量来表示平衡，遇到每个开括号时递增它，遇到每个闭括号时递减它。如果平衡在任何时候变为负数或最终不为零，则表达式不平衡。

实施

说明

• 程序定义了一个函数 areBracketsBalanced，它接受一个字符串的常量引用（表达式）作为其参数，并返回一个布尔值，指示表达式中的括号是否平衡。
• 在函数内部，变量 balance 初始化为零。然后函数使用基于范围的 for 循环遍历输入表达式中的每个字符。
• 对于每个字符，它检查它是否是开括号（'(', '{', 或 '['）。如果是，则递增 balance 变量。
• 另一方面，如果字符是闭括号（')', '}', 或 ']'），则递减 balance 变量。
• 此外，程序检查在迭代过程中 balance 是否在任何时候变为负数。如果是，则函数返回 false，表明表达式不平衡。
• 处理完表达式中的所有字符后，函数检查 balance 的最终值是否为零。如果是，则函数返回 true，表明表达式是平衡的。否则，它返回 false。
• 在 main 函数中，程序使用 std::cout 提示用户输入表达式。
• 然后它使用 std::cin 从用户读取输入表达式。
• 然后将输入的表达式传递给 areBracketsBalanced 函数，并使用结果通过 std::cout 输出表达式是平衡的还是不平衡的。

程序输出

时间复杂度和空间复杂度（不使用堆栈）

时间复杂度

该算法具有线性时间复杂度 O(n)，其中 'n' 是输入表达式的长度。这是因为表达式中的每个字符都被处理一次，并且执行的操作（递增、递减和比较）是常数时间操作。

空间复杂度

空间复杂度为 O(1)，这意味着算法使用的空间与输入表达式的大小无关。这是因为算法只使用一个整数变量（平衡）来跟踪括号的平衡。此变量所需的空间是恒定的，与输入表达式的长度无关。

结论

总之，检查表达式中括号平衡性的任务是计算机科学中的一个基本问题，在编译器设计、文本处理和解析等各种应用中发挥着至关重要的作用。这个问题的意义在于它能够确保表达式的句法正确性，防止可能导致程序中出现意外行为的错误。

本文讨论的算法方法包括基于堆栈的方法和递归算法，每种方法都有其自身的优点和权衡。例如，基于堆栈的方法利用堆栈的后进先出 (LIFO) 特性来有效地跟踪和验证表达式中括号的平衡性。

效率和简单性是选择适当算法来检查平衡括号的关键考虑因素。基于堆栈的方法因其简单性和线性时间复杂度而常受青睐。实际场景可能涉及额外的约束或考虑因素，这些因素会影响算法的选择，因此开发人员必须仔细评估所涉及的权衡。