常见数据结构的Python实现-栈
目录
1.1 基本概念
1.2 栈的实现
1.3 应用（括号匹配）
1.4 应用（中缀转后缀-整数）
1.5 应用（ 中缀转后缀-浮点数）
1) 拆分表达式
2) 中缀转后缀
1.6 应用（计算中缀表达式）
1) 计算后缀表达式
2) 计算中缀表达式
1. 栈
1.1 基本概念
栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。
- 栈顶（top）
- 栈底（bottom）
- 空栈：栈中元素个数为0
- 进栈（push），即插入操作
- 退栈（pop），即删除，出栈，弹栈
栈属于常见的一种线性结构，对于进栈和退栈而言，时间复杂度都为 O(1)
本例中所有的代码实现：git仓库地址：01-栈及其应用（计算中缀表达式）
1.2 栈的实现
class Stack(object):
def __init__(self):
"""
创建一个Stack类
对栈进行初始化参数设计
"""
self.stack = [] #存放元素的栈
def push(self, data):
"""
压入 push ：将新元素放在栈顶
当新元素入栈时，栈顶上移，新元素放在栈顶。
"""
self.stack.append(data)
def pop(self):
"""
弹出 pop ：从栈顶移出一个数据
- 栈顶元素拷贝出来
- 栈顶下移
- 拷贝出来的栈顶作为函数返回值
"""
# 判断是否为空栈
if self.stack:
return self.stack.pop()
else:
raise IndexError("从空栈执行弹栈操作")
def peek(self):
"""
查看栈顶的元素
"""
# 判断栈是否为空
if self.stack:
return self.stack[-1]
def is_empty(self):
"""
判断栈是否为空
"""
# 栈为非空时，self.stack为True，再取反，为False
return not bool(self.stack)
def size(self):
"""
返回栈的大小
"""
return len(self.stack)
1.3 应用（括号匹配）
目标：使用堆栈作为数据结构，检查括号字符串是否完全匹配
def balanced_parentheses(parentheses):
"""
由于只检查（）是否平衡，比较简单
思路是，
遇到（ 则将（ 进栈
遇到 ）则将当前栈顶的（ 出栈
如果是这两个符号以外的其他字符，则不执行任何操作
如果：
在执行 ）出栈的时候，栈已经为空，则表示符号不平衡【说明 ）更多】
在执行完所有的出栈后，栈不为空，则符号也不平衡【说明（ 更多】
"""
stack = Stack(limit=len(parentheses))
for p in parentheses:
if p == '(':
stack.push(p)
elif p == ')':
if stack.is_empty():
return False
stack.pop()
return stack.is_empty()
if __name__ == "__main__":
examples = ['(()())', '(()))', '((())', '(()((())())())', '() ( )']
print("运行结果：")
for example in examples:
print(example, ":", str(balanced_parentheses(example)))
运行结果：
1.4 应用（中缀转后缀-整数）
-
中缀表达式
平时所有的标准四则运算表达式，如
9 + (3-1) * 3 + 9/2
-
后缀表达式
转化为后缀表达式便于计算机计算
9 3 1 - 3 * + 9 2 / +
从左到右遍历中缀表达式的每个数字和符号
首先判断字符是否为数字：
- 是数字直接输出
- 不是数字再对字符串进行分析
- 左括号 ：左括号直接 压栈 ，如果栈顶元素已经为左括号
（
- 右括号 ：依次弹栈并输出栈里面的符号，直到遇到左括号
（
）
（
（
- 其他符号 【
+ - * /
- 入栈的条件是：当前符号的优先级 高于 栈顶元素或者为 空栈 ，否则执行 弹栈 操作，将依次弹出的符号，作为后缀表达式的一部分，一直弹栈，直到满足入栈要求为止
- 或者称之为，弹栈的条件为：当前字符的优先级 小于或等于 栈顶元素且栈非空，则执行弹栈，直到栈顶元素比当前字符优先级大，或者当前为空栈，才停止弹栈
- 如果栈顶元素为
（
- 左括号 ：左括号直接 压栈 ，如果栈顶元素已经为左括号
实现代码：
def infix2postfix(strings):
# 符号的优先级次序表
priority_dict = {
'(': 0,
'+': 10,
'-': 10,
'*': 20,
'/': 20,
')': 30}
# 首先创建空的 栈 数据结构，为后续做好准备
stack = Stack()
# 创建空的列表，存放后缀表达式
postfix = []
for char in strings:
# 先判断当前字符是否为数字，若是，该方法返回True，输出到后缀表达式
if char.isdigit():
postfix.append(char)
# 若不是数字，再进行其他分析
# 若是左括号，直接压栈
elif char == "(":
stack.push(char)
# 若是右括号，则依次弹栈，直到遇到左括号
elif char == ")":
while stack.peek() != "(":
pop_char = stack.pop()
postfix.append(pop_char)
# 将符号弹出到后缀表达式后，再将（ 弹栈，注意，只弹栈，不输出到后缀表达式
stack.pop()
# 如果是加减乘除
elif (char == '+' or char == '-' or char == '*' or char == '/'):
# 如果当前符号的优先级小于等于栈顶元素，且栈为非空，则弹栈
if (stack.is_empty() != True) and (priority_dict[char] <= priority_dict[stack.peek()]):
while (stack.is_empty() != True) and (priority_dict[char] <= priority_dict[stack.peek()]):
pop_char = stack.pop()
postfix.append(pop_char)
# 一直弹栈到满足压栈的要求为止，则将当前字符压栈
stack.push(char)
# 如果当前字符本身优先级就比栈顶元素优先级高，或者当前为空栈，则直接执行压栈操作
else:
stack.push(char)
# 如果在遍历完表达式后栈不为空，则依次弹栈
while stack.is_empty() != True:
postfix.append(stack.pop())
print(postfix)
return postfix
if __name__ == "__main__":
infix2postfix("9+(3-1)*3+9/2")
- 运行结果：
['9', '3', '1', '-', '3', '*', '+', '1', '9', '/', '+']
思考一下，上述程序有问题，
1）只能处理10以内的加减乘除，因为程序是一位一位读取的，因此，会将10拆成 1 和 0
如：
infix2postfix("9+(3-1)*3+10/2")
# 输出结果为：
['9', '3', '1', '-', '3', '*', '+', '1', '0', '2', '/', '+']
2）不能进行带有小数点的浮点数的运算
infix2postfix("9.2+(3-1)*3+9/2")
# 输出结果为：
['9', '2', '3', '1', '-', '3', '*', '+', '9', '2', '/', '+']
后续对这两个存在的问题进行改进
1.5 应用（ 中缀转后缀-浮点数）
要解决上面的两个问题，需要将字符串组成的中缀表达式正确地
拆分需要将字符串拆解称为单个字符组成的列表
要实现的效果是：
- 输入表达式字符串
- 拆分成数字和符号组成的字符串列表
1) 拆分表达式
实现代码：
def Strng2ListofString(aString):
"""
将一个中缀表达式拆分
数字（包括整数和浮点数）、符号 拆分成单个字符
"""
symbol_list = ['+', '-', '*', '/', '(', ')']
# 在最后补全符号，便于后续操作
aString = aString + '+'
# 存放拆分后的字符
char_list = []
single_char = ""
for char in aString:
# 如果char不在指定的符号集中，则认为是数字
if char not in symbol_list:
single_char += char
else:
char_list.append(single_char)
char_list.append(char)
single_char = ""
# 删掉空白字符串
char_list = [char for char in char_list if char != '']
# 删掉多余的补充的加号+
char_list = char_list[:-1]
return char_list
2) 中缀转后缀
有了上述的拆分函数，那么就能正确地执行中缀转后缀了
由于中缀转后缀规则中，对数字和符号的处理不同，
这里需要有一个函数，实现判断拆分后的字符串是识别为数字还是符号，该功能实现为：
def is_number(aString):
"""
判断一个字符串是否是一个数字或者浮点数
是，返回True
否，返回False
"""
try:
float(aString)
return True
except:
return False
代码实现：
def infix2postfix(strings):
"""
输入：未经处理的原始中缀表达式
输出：后缀表达式（拆成单个字符组成列表）
"""
# 给定符号的优先级次序，后续压栈，弹栈规则使用
priority_dict = {
'(': 0,
'+': 10,
'-': 10,
'*': 20,
'/': 20,
')': 30, }
# 将数据字符串表达式处理为 单字符列表
strings = Strng2ListofString(strings)
# 为了兼顾第一个符号为负号-的情况
# 对于-2*3这种，改写成 0-2*3 的形式
if strings[0] == '-':
strings.insert(0, '0')
# 首先创建空的 栈 数据结构，为后续做好准备
stack = Stack()
# 创建空的列表，存放后缀表达式
postfix = []
for char in strings:
# 先判断当前字符是否为数字，若是，该方法返回True，直接附加到后缀表达式中去
if is_number(char):
postfix.append(char)
# 若不是数字，再进行其他分析
# 若是左括号，直接压栈
elif char == "(":
stack.push(char)
# 若是右括号，则依次弹栈，直到遇到左括号
elif char == ")":
while stack.peek() != "(":
postfix.append(stack.pop())
# 将符号弹出到后缀表达式后，再将（ 弹栈，注意，只弹栈，不输出到后缀表达式
stack.pop()
# 如果是加减乘除
elif (char == '+' or char == '-' or char == '*' or char == '/'):
# 如果当前符号的优先级小于等于栈顶元素，且栈为非空，则弹栈
if (stack.is_empty() != True) and (priority_dict[char] <= priority_dict[stack.peek()]):
while (stack.is_empty() != True) and (priority_dict[char] <= priority_dict[stack.peek()]):
postfix.append(stack.pop())
# 一直弹栈到满足压栈的要求为止，则将当前字符压栈
stack.push(char)
# 如果当前字符本身优先级就比栈顶元素优先级高，或者当前为空栈，则直接执行压栈操作
else:
stack.push(char)
# 如果在遍历完表达式后栈不为空，则依次弹栈
while stack.is_empty() != True:
postfix.append(stack.pop())
return postfix
运行结果：
能够正确地处理浮点数和大于1位的数字
最后，得到了后缀表达式就可以轻松地利用栈进行运算，计算得出表达式的值
1.6 应用（计算中缀表达式）
将上述的代码组合起来，先由中缀表达式得到后缀表达式，再计算后缀表达式即可
1) 计算后缀表达式
后缀表达式，例如：
9 3 1 - 3 * + 9 2 / +
后缀表达式的计算规则为：
- 从左到右遍历表达式的每个数字和符号
- 遇到数字就进栈
-
遇到符号，就将处于栈顶的两个数字进行运算，（top数为操作数，second_top数为被操作数）
如减法，除法，top数为减数、除数；second_top数为被减数、被除数
运算结果进栈
- 一直到遍历结束，将最终得到的计算结果出栈
# 输入后缀表达式进行计算
def cal_postfix(postfix_list):
"""
输入后缀表达式
输出计算结果
"""
stack = Stack()
for char in postfix_list:
if is_number(char):
stack.push(char)
elif char == '+':
top_num = float(stack.pop())
sec_num = float(stack.pop())
res = sec_num + top_num
stack.push(res)
elif char == '-':
top_num = float(stack.pop())
sec_num = float(stack.pop())
res = sec_num - top_num
stack.push(res)
elif char == '*':
top_num = float(stack.pop())
sec_num = float(stack.pop())
res = sec_num * top_num
stack.push(res)
elif char == '/':
top_num = float(stack.pop())
sec_num = float(stack.pop())
res = sec_num / top_num
stack.push(res)
res = stack.pop()
return res
2) 计算中缀表达式
将上面函数组合即可
代码实现：
def cal_infix(aString):
"""
输入：原始的中缀表达式，
输出：表达式的计算结果
中间步骤：
1.将原始中缀表达式转写为后缀表达式（包含了首位为负号‘-’的处理）infix2postfix
2.计算后缀表达式 cal_postfix
"""
return cal_postfix(infix2postfix(aString))
效果：