3.6. 简单的括号匹配¶

3.6. Simple Balanced Parentheses

原文: https://runestone.academy/ns/books/published/pythonds3/BasicDS/SimpleBalancedParentheses.html?mode=browsing

中文英文

现在我们将关注于使用栈来解决实际的计算机科学问题。你可能已经写过类似这样的算术表达式：

\[(5 + 6) * (7 + 8) / (4 + 3)\]

在这些表达式中，括号用于排序操作的执行。你也可能在编程语言如 Lisp 中有过一些编程经验，比如有如下构造：

(defun square(n)
        (* n n))

这定义了一个名为 square 的函数，它会返回其参数 n 的平方。Lisp 以使用大量括号而闻名。

在这两个示例中，括号必须以平衡的方式出现。平衡的括号 意味着每个开括号都有一个对应的闭括号，并且括号对是正确嵌套的。考虑以下正确平衡的括号字符串：

(()()()())

(((())))

(()((())()))

将这些与以下不平衡的括号字符串进行比较：

    ((((((())

    ()))

    (()()(()

区分正确平衡的括号和不平衡的括号是识别许多编程语言结构的重要部分。

挑战在于编写一个算法，从左到右读取括号字符串，并决定这些符号是否平衡。要解决这个问题，我们需要做一个重要的观察。当你从左到右处理符号时，最新的开括号必须与下一个闭括号匹配（见 Figure 4）。此外，第一个处理的开符号可能需要等到最后一个符号才会有匹配。闭符号与开符号的匹配是按出现的相反顺序进行的；它们是从内部向外匹配的。这是栈可以用来解决问题的线索。

一旦你同意栈是保持括号的适当数据结构，算法的描述就是直接的。从一个空栈开始，从左到右处理括号字符串。如果符号是开括号，则将其推入栈中，表示稍后需要出现一个相应的闭符号。另一方面，如果符号是闭括号，则弹出栈。只要可以弹出栈以匹配每个闭符号，括号就保持平衡。如果在任何时候栈中没有开符号来匹配一个闭符号，则字符串不平衡。在字符串结束时，当所有符号都被处理完后，栈应该是空的。实现这个算法的 Python 代码如下所示（ActiveCode 1）。

Activity: 3.6.1 解决平衡括号问题
from pythonds3.basic import Stack


def par_checker(symbol_string):
    s = Stack()
    for symbol in symbol_string:
        if symbol == "(":
            s.push(symbol)
        else:
            if s.is_empty():
                return False
            else:
                s.pop()

    return s.is_empty()


print(par_checker("((()))"))  # 预期输出 True
print(par_checker("((()()))"))  # 预期输出 True
print(par_checker("(()"))  # 预期输出 False
print(par_checker(")("))  # 预期输出 False

这个函数 par_checker 假设 Stack 类是可用的，并返回一个布尔值，表示括号字符串是否平衡。如果当前符号是 (，则将其推入栈中（第 7 到 8 行）。另外注意第 13 行的 pop 只是从栈中移除一个符号。返回的值没有使用，因为我们知道它必须是之前看到的开符号。如果在处理完 symbol_string 之前栈变为空，则说明有太多的闭括号，字符串不平衡，因此我们立即返回 False（第 11 行）。在结束时（第 15 行），只要栈已完全清空，字符串就代表一个正确平衡的括号序列。

We now turn our attention to using stacks to solve real computer science problems. You have no doubt written arithmetic expressions such as

\[(5 + 6) * (7 + 8) / (4 + 3)\]

where parentheses are used to order the performance of operations. You may also have some experience programming in a language such as Lisp with constructs like

(defun square(n)
        (* n n))

This defines a function called square that will return the square of its argument n. Lisp is notorious for using lots and lots of parentheses.

In both of these examples, parentheses must appear in a balanced fashion. Balanced parentheses means that each opening symbol has a corresponding closing symbol and the pairs of parentheses are properly nested. Consider the following correctly balanced strings of parentheses:

(()()()())

(((())))

(()((())()))

Compare those with the following, which are not balanced:

    ((((((())

    ()))

    (()()(()

The ability to differentiate between parentheses that are correctly balanced and those that are unbalanced is an important part of recognizing many programming language structures.

The challenge then is to write an algorithm that will read a string of parentheses from left to right and decide whether the symbols are balanced. To solve this problem we need to make an important observation. As you process symbols from left to right, the most recent opening parenthesis must match the next closing symbol (see Figure 4). Also, the first opening symbol processed may have to wait until the very last symbol for its match. Closing symbols match opening symbols in the reverse order of their appearance; they match from the inside out. This is a clue that stacks can be used to solve the problem.

Once you agree that a stack is the appropriate data structure for keeping the parentheses, the statement of the algorithm is straightforward. Starting with an empty stack, process the parenthesis strings from left to right. If a symbol is an opening parenthesis, push it on the stack as a signal that a corresponding closing symbol needs to appear later. If, on the other hand, a symbol is a closing parenthesis, pop the stack. As long as it is possible to pop the stack to match every closing symbol, the parentheses remain balanced. If at any time there is no opening symbol on the stack to match a closing symbol, the string is not balanced properly. At the end of the string, when all symbols have been processed, the stack should be empty. The Python code to implement this algorithm is shown in ActiveCode 1.

Activity: 3.6.1 Solving the Balanced Parentheses Problem
from pythonds3.basic import Stack


def par_checker(symbol_string):
    s = Stack()
    for symbol in symbol_string:
        if symbol == "(":
            s.push(symbol)
        else:
            if s.is_empty():
                return False
            else:
                s.pop()

    return s.is_empty()


print(par_checker("((()))"))  # expected True
print(par_checker("((()()))"))  # expected True
print(par_checker("(()"))  # expected False
print(par_checker(")("))  # expected False

This function, par_checker, assumes that a Stack class is available and returns a Boolean result as to whether the string of parentheses is balanced. If the current symbol is (, then it is pushed on the stack (lines 7--8). Note also in line 13 that pop simply removes a symbol from the stack. The returned value is not used since we know it must be an opening symbol seen earlier. If the stack becomes empty before we reach the end of the symbol_string, then there are too many closing parentheses and the string is not balanced, so we immediately return False (line 11). At the end (line 15), the string represents a correctly balanced sequence of parentheses as long as the stack has been completely cleaned off.

最后更新: 2024年9月12日
创建日期: 2024年9月9日