Python栈应用

本文将从多个方面对Python栈应用进行详细阐述。

一、栈的概念

栈（Stack）是一种后进先出（Last In, First Out）的数据结构，类似于我们日常生活中的一堆书叠放在一起，只能从最后放入的书开始取出。栈的特点是元素的插入和删除只能在栈顶进行。

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 is_matched(expression): stack = Stack() for char in expression: if char in '([{': stack.push(char) elif char in ')]}': if stack.is_empty(): return False if not is_pair(stack.pop(), char): return False return stack.is_empty() def is_pair(left, right): pairs = {'(': ')', '[': ']', '{': '}'} return pairs[left] == right print(is_matched('()')) # True print(is_matched('[(])')) # False

2、逆波兰表达式计算

逆波兰表达式是一种不需要括号的数学表达式表示方法，栈可以用于计算逆波兰表达式。遍历表达式，当遇到数字时，将数字入栈；当遇到操作符时，弹出栈顶的两个数字进行计算，然后将结果入栈。

 def eval_rpn(expression): stack = Stack() for token in expression.split(): if token.isdigit(): stack.push(int(token)) else: right = stack.pop() left = stack.pop() result = calculate(left, right, token) stack.push(result) return stack.pop() def calculate(left, right, operator): if operator == '+': return left + right elif operator == '-': return left - right elif operator == '*': return left * right elif operator == '/': return left / right print(eval_rpn('3 4 + 5 *')) # 35 print(eval_rpn('4 2 * 3 +')) # 11