Python数据结构与算法中的栈详解(3)

在前两篇文章中，我们介绍了栈的基本概念、实现方式和应用场景。在本篇文章中，我们将深入探讨栈的一些高级应用，包中缀表达式转后缀表达式、后缀表达式求值和括号匹配等。

中缀表达式转后缀表达

中缀表达式是我们平常使用的表达式，例如3 + 4 * 5。但是，中缀表达式不方便计算机进行计算，因此我们需要将中缀表达式转换为后缀表达式。缀表达式也称为逆波兰表达式，它的计算方式更加方便。例如，上面的中缀表达式可以转换为后缀表达式3 4 5 * +。

下面是中缀表达式后缀表达式的算法：

初始化一个空栈和一个空列表。
从左到右扫描中缀表达式的每个素。
如果当前元素是数字，将其添加到输出列表中。
如果当前元素是左括号，将其压入栈中。
如果当前元素是右括号，则将栈中的元素弹出并添加到输出列表中，直到遇到左括号。左括号不添加到输出列表中。
如果当前元素是运算符，比较其与栈顶运算符的优先级：
如果栈顶运算符优先级较高或相等，则将其弹出并添加到输出列表中，直到栈为空或栈顶运算符优先级较低。
将当前运算符压入栈中。
如果中缀表达式扫描完毕，但栈中仍有运算符，将它们依次弹出并添加到输出列表中。
输出列表中的元素就是后缀表达式。

下面是一个示例，演示如何将中缀表达式3 + 4 * 5转换为后缀表达式：

初始化一个空栈和一个空列表。
从左到右描中缀表达式的每个元素。
3是数字，将其添加到输出列表中。
+是运算符，将其压入栈中。
4是数字，将其添加到输出列表中。
*是运算符，比较其与栈顶运算符的优先级，栈顶运算符+优先级较低，将*压入栈中。
5是数字，将其添加到输出列表中。
中缀表达式扫描完毕，但栈中仍有运算符，将它们依次弹出并添加到输出列表中。栈中只有一个运算符*，将其弹出并添加到输出列表中。
输出列表中的元素就是后缀表达式3 4 5 * +。

下面是Python代码实现中缀表达式转后缀表达式：

def infix_to_postfix(infix_expr):
    # 运算符优先级
    prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
    # 初始化一个空栈和空列表
    op_stack = []
    postfix_list = []
    # 将中缀表达式转换为列表
    infix_list = infix_expr.split()

    for token in infix_list:
        if token.isdigit():
            # 如果当前元素是数字，将其添加到输出列表中
            postfix_list.append(token)
        elif token == '(':
            # 如果当前元素是左括号，将其压入栈中
            op_stack.append(token)
        elif token == ')':
            # 如果当前元素是右括号，则将栈中的元素弹出并添加到输出列表中，直到遇到左括号
            top_token = op_stack.pop()
            while top_token != '(':
                postfix_list.append(top_token)
                top_token = op_stack.pop()
        else:
            # 如果当前元素是运算符
            while op_stack and prec[op_stack[-1]] >= prec[token]:
                # 比较其与栈顶运算符的优先级
                postfix_list.append(op_stack.pop())
            op_stack.append(token)

    # 将栈中剩余的运算符弹出并添加输出列表中
    while op_stack:
        postfix_list.append(op_stack.pop())

    # 输出列表中的元素就是后缀表达式
    return ' '.join(postfix_list)

后缀表达式求值

后缀表达式的计算方式更加方便，可以使用栈来实现。下面是后缀表达式求值的算法：

初始化一个空栈。
从左到右扫描后缀表达式的每个元素。
3 如果当前元素是数字，将其压入栈中。
如果当前元素是运算符，弹出栈顶的两个元素，进行运，并将结果压入栈中。
扫描完毕后，栈中只剩下一个元素，即为后缀表达式的计算结果。

下面是一个示例，演示如何计算后缀表达式3 4 5 * +的值：

初始化一个空栈。
从左到右扫描后缀表达式的每个元素。
3是数字，将其压入栈中。
4是数字，将其压入栈中。
5是数字，将其压入栈中。
*是运算符，弹出栈顶的两个元素4和5，进行运算4 * 5 = 20，并将结果20压入栈中。
+是运算符，弹出栈顶的两个元素3和20，进行运算3 + 20 = 23，并将结果23压入栈中。
扫描完毕后，栈中只剩下一个元素23，即为后缀表达式的计算结果。

下面是Python代码实现后缀表达式求值：

def postfix_eval(postfix_expr):
    # 初始化一个空栈
    operand_stack = []
    # 将后缀表达式转换为列表
    postfix_list = postfix_expr.split()

    for token in postfix_list:
        if token.isdigit():
            # 如果当前元素是数字，将其压入栈中
            operand_stack.append(int(token))
        else:
            # 如果当前元素是运算符，弹出栈顶的两个元素，进行运算，并将结果压入栈中
            operand2 = operand_stack.pop()
            operand1 = operand_stack.pop()
            result = do_math(token, operand1, operand2)
            operand_stack.append(result)

    # 栈中只剩下一个元素，即为后缀表达式的计算结果
    return operand_stack.pop()

def do_math(op, op1, op2):
    if op == '*':
        return op1 * op2
    elif op == '/':
        return op1 / op2
    elif op == '+':
        return op1 + op2
    else:
        return op1 - op2

括号匹配

括号匹配是栈的一个经典应用。我们可以使用栈来判断一个字符串中的括号是否匹配。下面是括号匹配的算法：

初始化一个空栈。
从左到右扫描字符串中的每个字符。
如果当前字符是左括号，将其压入栈中。
如果当前字符是右括号，弹出栈顶元素。如果栈顶元素不是相应的左括号，则括号不匹配。
扫描完毕，如果栈为空，则括号匹配。

下面是一个示例，演示如何判断字符串((()))中的括号是否匹配：

初始化一个空栈。
从左到右扫描字符串中的每个字符。
(是左括号，将其压入栈中。
(是左括号，将其压入栈中。
(是左括号，将其压入栈中。
)是右括号，弹出栈顶元素(。
)是右括号，弹出栈顶元素(。
是右括号，弹出栈顶元素(`。
扫描完毕后，如果栈为空，则括号匹配。

下面是Python代码实现括号匹配：

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()

示例说明

下面是两个示例，演示如何使用栈实现中缀表达式转后缀表达式和后缀表达式求值：

示例1：中缀表达式转后缀表达式

def infix_to_postfix(infix_expr):
    # 运算符优先级
    prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
    # 初始化一个空栈和一个空列表
    op_stack = []
    postfix_list = []
    # 将中缀表达式转换为列表
    infix_list = infix_expr.split()

    for token in infix_list:
        if token.isdigit():
            # 如果当前元素是数字，将其添加到输出列表中
            postfix_list.append(token)
        elif token == '(':
            # 如果当前元素是左括号，将其压入栈中
            op_stack.append(token)
        elif token == ')':
            # 如果当前元素是右括号，则将栈中的元素弹出并添加到列表中，直到遇到左括号
            top_token = op_stack.pop()
            while top_token != '(':
                postfix_list.append(top_token)
                top_token = op_stack.pop()
        else:
            # 如果当前元素是运算符
            while op_stack and prec[op_stack[-1]] >= prec[token]:
                # 比较其与栈顶运算符的优先级
                postfix_list.append(op_stack.pop())
            op_stack.append(token)

    # 将栈中剩余的运算符弹出并添加到输出列表中
    while op_stack:
        postfix_list.append(op_stack.pop())

    # 输出列表中的元素就是后缀表达式
    return ' '.join(postfix_list)

infix_expr = '3 + 4 * 5'
postfix_expr = infix_to_postfix(infix_expr)
print(postfix_expr)  # 输出：3 4 5 * +

在这个示例中，我们使用栈实现了中缀表达式转后缀表达式。我们将中缀表达式3 + 4 * 5转换为后缀表达式3 4 5 * +。

示例2：后缀表达式求值

def postfix_eval(postfix_expr):
    # 初始化一个空栈
    operand_stack = []
    # 将后缀表达式转换为列表
    postfix_list = postfix_expr.split()

    for token in postfix_list:
        if token.isdigit():
            # 如果当前元素是数字，将其压入栈中
            operand_stack.append(int(token))
        else:
            # 如果当前元素是运算符，弹出栈顶的两个元素，进行运算，并将结果压入栈中
            operand2 = operand_stack.pop()
            operand1 = operand_stack.pop()
            result = do_math(token, operand1, operand2)
            operand_stack.append(result)

    # 栈中只剩下一个元素，即为后缀表达式的计算结果
    return operand_stack.pop()

def do_math(op, op1, op2):
    if op == '*':
        return op1 * op2
    elif op == '/':
        return op1 / op2
    elif op == '+':
        return op1 + op2
    else:
        return op1 - op2

postfix_expr = '3 4 5 * +'
result = postfix_eval(postfix_expr)
print(result)  # 输出：23

在这个示例中，我们使用栈实现了后缀表达式求值。我们计算后缀表达式3 45 * +的值，结果为23。

Python数据结构与算法中的栈详解(3)

中缀表达式转后缀表达

后缀表达式求值

括号匹配

示例说明

示例1：中缀表达式转后缀表达式

示例2：后缀表达式求值

你可能也喜欢

Python 打包多项数据并映射

计算两个多维NumPy数组的克朗克乘积

使用Python将Exception异常错误堆栈信息写入日志文件