Python算法实战系列：栈(Python算法实战：栈的应用与解析)

原创

ithorizon 6个月前 (10-21) 阅读数 12 #后端开发

Python算法实战：栈的应用与解析

一、栈的基本概念

栈（Stack）是一种线性数据结构，它遵循先入后出（First In Last Out，FILO）的原则。栈的操作核心包括两种：压栈（push）和出栈（pop）。压栈是指在栈顶插入一个元素，而出栈是指从栈顶删除一个元素。栈广泛应用于算法和程序设计中的各种场景，如递归、逆序输出、括号匹配等。

二、Python中的栈实现

Python中可以使用列表（list）来实现栈的功能。以下是一个简洁的栈实现示例：


class Stack:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return len(self.items) == 0
    def push(self, item):
        self.items.append(item)
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            return None
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            return None
    def size(self):
        return len(self.items)

三、栈的应用实例

1. 逆序输出

栈的一个典型应用是逆序输出一个序列。以下是一个逆序输出字符串的例子：


def reverse_string(s):
    stack = Stack()
    for char in s:
        stack.push(char)
    
    reversed_str = ""
    while not stack.is_empty():
        reversed_str += stack.pop()
    
    return reversed_str
# 测试
s = "Hello, World!"
print(reverse_string(s))  # 输出: "!dlroW ,olleH"

2. 括号匹配

栈可以用来检查一个字符串中的括号是否匹配。以下是一个括号匹配的例子：


def is_balanced(s):
    stack = Stack()
    left_chars = ['(', '[', '{']
    right_chars = [')', ']', '}']
    for char in s:
        if char in left_chars:
            stack.push(char)
        elif char in right_chars:
            if stack.is_empty():
                return False
            left_char = stack.pop()
            if left_chars.index(left_char) != right_chars.index(char):
                return False
    return stack.is_empty()
# 测试
s = "{[()]}{[()]}"
print(is_balanced(s))  # 输出: True

3. 递归

递归是一种常见的算法设计方法，它利用栈来实现函数的嵌套调用。以下是一个计算阶乘的递归函数：


def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)
# 测试
print(factorial(5))  # 输出: 120

四、栈的进阶应用

1. 后缀表达式求值

后缀表达式（Reverse Polish Notation，RPN）是一种不需要括号的数学表达式即方法。以下是一个后缀表达式求值的例子：


def evaluate_rpn(expression):
    stack = Stack()
    for token in expression.split():
        if token.isdigit():
            stack.push(int(token))
        else:
            right = stack.pop()
            left = stack.pop()
            if token == '+':
                stack.push(left + right)
            elif token == '-':
                stack.push(left - right)
            elif token == '*':
                stack.push(left * right)
            elif token == '/':
                stack.push(left / right)
    return stack.pop()
# 测试
expression = "3 4 + 5 * 2 -"
print(evaluate_rpn(expression))  # 输出: 9

2. 中缀表达式转后缀表达式

将中缀表达式变成后缀表达式是栈的另一个应用。以下是一个转换函数的例子：


def infix_to_rpn(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    stack = Stack()
    output = []
    for char in expression:
        if char.isdigit():
            output.append(char)
        elif char in precedence:
            while (not stack.is_empty() and stack.peek() in precedence and
                   precedence[char] <= precedence[stack.peek()]):
                output.append(stack.pop())
            stack.push(char)
        elif char == '(':
            stack.push(char)
        elif char == ')':
            while not stack.is_empty() and stack.peek() != '(':
                output.append(stack.pop())
            stack.pop()
    while not stack.is_empty():
        output.append(stack.pop())
    return ' '.join(output)
# 测试
expression = "( 3 + 4 ) * 5 - 2"
rpn_expression = infix_to_rpn(expression)
print(rpn_expression)  # 输出: "3 4 + 5 * 2 -"