python 栈

       栈是线性的集合，其中，访问都严格的限制在一端，也叫作顶（top）。栈是遵从后进先出（LIFO）的协议，从栈放入项和从栈删除项的操作分别叫压人（push）和弹出（pop）。

       栈并不是Python的内建类型，Python程序员在必要的时候可以使用列表来模拟基于数组的栈。如果将列表的末尾看作是栈的顶，列表方法append就是将元素压入到栈中，而列表方法pop会删除并返回栈顶的元素。

       栈的应用：

• 将中缀表达式转换为后缀表达式，并且计算后缀表达式
• 回溯算法
• 管理计算机内存以支持函数和方法调用
• 支持文本编辑器、字处理程序、电子表格程序、绘图程序或类似的应用程序中的撤销功能
• 维护Web浏览器所访问过的连接的历史记录

一、中缀表达式转换为后缀表达式 

中缀表达式转后缀表达式的规则：

1.遇到操作数，直接输出； 
2.栈为空时，遇到运算符，入栈； 
3.遇到左括号，将其入栈； 
4.遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出； 
5.遇到其他运算符’+”-”*”/’时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈； 
6.最终将栈中的元素依次出栈，输出。 
经过上面的步骤，得到的输出既是转换得到的后缀表达式。 

def middle2behind(expresssion):  result = []             # 结果列表stack = []              # 栈for item in expression: if item.isnumeric():      # 如果当前字符为数字那么直接放入结果列表result.append(item) else:                     # 如果当前字符为一切其他操作符if len(stack) == 0:   # 如果栈空，直接入栈stack.append(item)elif item in '*/(':   # 如果当前字符为*/（，直接入栈stack.append(item)elif item == ')':     # 如果右括号则全部弹出（碰到左括号停止）t = stack.pop()while t != '(':   result.append(t)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！