跳转至

3.7. 符号匹配（一般情况）

3.7. Balanced Symbols (A General Case)

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

上面讨论的平衡括号问题是许多编程语言中出现的更一般情况的特例。平衡和嵌套不同类型的开闭符号的普遍问题在编程中经常出现。例如，在 Python 中，方括号 [ 和 ] 用于列表；大括号 { 和 } 用于集合和字典；而圆括号 ( 和 ) 用于元组和算术表达式。只要每种符号保持其自身的开闭关系，就可以混合使用这些符号。像以下这样的符号串：

{ { ( [ ] [ ] ) } ( ) }

[ [ { { ( ( ) ) } } ] ]

[ ] [ ] [ ] ( ) { }

是正确平衡的，因为每个开符号都有一个对应的闭符号，并且符号类型也匹配。

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

( [ ) ]

( ( ( ) ] ) )

[ { ( ) ]

前一节中简单的括号检查器可以很容易地扩展以处理这些新的符号类型。回顾一下，每个开符号都简单地推入栈中，以等待后续出现的匹配闭符号。当闭符号出现时，唯一的区别是我们必须检查它是否正确匹配栈顶的开符号。如果两个符号不匹配，则字符串不平衡。再次强调，如果处理完整个字符串后栈中没有剩余符号，则字符串是正确平衡的。

实现这个功能的 Python 程序如下所示（ActiveCode 1）。唯一的变化出现在第 13 行，我们调用了一个辅助函数 matches 来帮助符号匹配。每个从栈中移除的符号必须检查是否与当前的闭符号匹配。如果发生不匹配，平衡检查器将立即返回 False。

Activity: 3.7.1 解决一般的符号平衡问题
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from pythonds3.basic import Stack


def balance_checker(symbol_string):
    s = Stack()
    for symbol in symbol_string:
        if symbol in "([{":
            s.push(symbol)
        else:
            if s.is_empty():
                return False
            else:
                if not matches(s.pop(), symbol):
                    return False

    return s.is_empty()

def matches(sym_left, sym_right):
    all_lefts = "([{"
    all_rights = ")]}"
    return all_lefts.index(sym_left) == all_rights.index(sym_right)


print(balance_checker('{({([][])}())}'))
print(balance_checker('[{()]'))

这两个示例表明，栈是处理计算机科学中语言构造的重要数据结构。几乎所有你能想到的记法都有一些需要按平衡顺序匹配的嵌套符号。在计算机科学中，栈还有许多其他重要的用途。我们将在接下来的部分继续探讨这些用途。

The balanced parentheses problem shown above is a specific case of a more general situation that arises in many programming languages. The general problem of balancing and nesting different kinds of opening and closing symbols occurs frequently. For example, in Python square brackets, [ and ], are used for lists; curly braces, { and }, are used for sets and dictionaries; and parentheses, ( and ), are used for tuples and arithmetic expressions. It is possible to mix symbols as long as each maintains its own open and close relationship. Strings of symbols such as

{ { ( [ ] [ ] ) } ( ) }

[ [ { { ( ( ) ) } } ] ]

[ ] [ ] [ ] ( ) { }

are properly balanced in that not only does each opening symbol have a corresponding closing symbol, but the types of symbols match as well.

Compare those with the following strings that are not balanced:

( [ ) ]

( ( ( ) ] ) )

[ { ( ) ]

The simple parentheses checker from the previous section can easily be extended to handle these new types of symbols. Recall that each opening symbol is simply pushed on the stack to wait for the matching closing symbol to appear later in the sequence. When a closing symbol does appear, the only difference is that we must check to be sure that it correctly matches the type of the opening symbol on top of the stack. If the two symbols do not match, the string is not balanced. Once again, if the entire string is processed and nothing is left on the stack, the string is correctly balanced.

The Python program to implement this is shown in ActiveCode 1. The only change appears in line 13 where we call a helper function, matches, to assist with symbol-matching. Each symbol that is removed from the stack must be checked to see that it matches the current closing symbol. If a mismatch occurs, the balance checker returns False immediately.

Activity: 3.7.1 Solving the General Balanced Symbol Problem
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from pythonds3.basic import Stack


def balance_checker(symbol_string):
    s = Stack()
    for symbol in symbol_string:
        if symbol in "([{":
            s.push(symbol)
        else:
            if s.is_empty():
                return False
            else:
                if not matches(s.pop(), symbol):
                    return False

    return s.is_empty()

def matches(sym_left, sym_right):
    all_lefts = "([{"
    all_rights = ")]}"
    return all_lefts.index(sym_left) == all_rights.index(sym_right)


print(balance_checker('{({([][])}())}'))
print(balance_checker('[{()]'))

These two examples show that stacks are very important data structures for the processing of language constructs in computer science. Almost any notation you can think of has some type of nested symbol that must be matched in a balanced order. There are a number of other important uses for stacks in computer science. We will continue to explore them in the next sections.

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