利用stack结构,将中缀表达式转换为后缀表达式并求值的算法实现
2024-10-14 21:29:04
#!/usr/bin/env python # -*- coding: utf-8 -*- # learn <<Problem Solving with Algorithms and Data Structures>> # Release 3.0 # chengang882 @ 2016-12-20 # 它可以将常见的中缀表达式转换成后缀表达式,并计算这个表达示的值 # Completed implementation of a stack ADT #数据结构 class Stack(object): def __init__(self): self.items = [] def is_empty(self): return self.items == [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return self.items[len(self.items)-1] def size(self): return len(self.items) # 实现中缀表达式转换为后缀表达式 def infix_to_postfix(infix_expr): prec = {} prec["*"] = 3 prec["/"] = 3 prec["+"] = 2 prec["-"] = 2 prec["("] = 1 op_stack = Stack() postfix_list = [] # 一定要有空格切割,显得不完美 token_list = infix_expr.split() for token in token_list: if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789": postfix_list.append(token) elif token == "(": op_stack.push(token) elif token == ")": top_token = op_stack.pop() while top_token != "(": postfix_list.append(top_token) top_token = op_stack.pop() else: while (not op_stack.is_empty()) and \ (prec[op_stack.peek()] >= prec[token]): postfix_list.append(op_stack.pop()) op_stack.push(token) while not op_stack.is_empty(): postfix_list.append(op_stack.pop()) print(" ".join(postfix_list)) return " ".join(postfix_list) # 计算后缀表达式的值 def postfix_eval(postfix_expr): operand_stack = Stack() token_list = postfix_expr.split() for token in token_list: if token in "0123456789": operand_stack.push(int(token)) else: operand2 = operand_stack.pop() operand1 = operand_stack.pop() # 还是将后缀换成中缀再计算 result = do_math(token, operand1, operand2) operand_stack.push(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 elif op == "-": return op1 - op2 else: raise("ERROR") if __name__ == "__main__": print(postfix_eval(infix_to_postfix("5 * 8 + 2 * 3"))) infix_to_postfix("( A + B ) * C - ( D - E ) * ( F + G )") print(postfix_eval('7 8 + 3 2 + /'))
输出:
>>> 5 8 * 2 3 * + 46 A B + C * D E - F G + * - 3 >>>
最新文章
- boxsizing属性 IE盒模型和标准盒模型
- xml文件格式说明
- wydomain
- javascript图片库
- 由浅入深探究mysql索引结构原理、性能分析与优化 转
- InnoDB外键使用小结
- [AngularJS + Webpack] Requiring Templates
- 针对上一篇文章中的代码,想出的重构方案(python实现)
- mvc 解决StyleBundle中 图片绝对路径 装换成相对路径的问题 CssRewriteUrlTransform
- /var/cache/apt/archives/lock - open
- JAR、WAR、EAR的使用和区别
- piggy.lzo
- Egret 4.x 和 5.x 项目共存的方法
- linux用ssh登录卡或者慢
- Linux 命令 及 简单操作 学习
- (转-经典-数据段)C++回顾之static用法总结、对象的存储,作用域与生存期
- 有关O_APPEND标志和lseek()的使用
- Dhaka2011
- nginx+Uwsgi+Django总结与分析
- POJ 1577Falling Leaves(二叉树的建立)
热门文章
- UIDynamic(重力行为+碰撞检测)
- html5离线应用和缓存
- Codeforces Round #342 (Div. 2) B. War of the Corporations(贪心)
- excel学习
- 使用XAMPP创建本地浏览器经验
- python 模块基础介绍
- @SuppressWarnings的参数
- [译]Testing Node.js With Mocha and Chai
- undefined method `environment&#39; for nil:NilClass when importing Bootstrap into rails
- 微信小程序开发视频教程新鲜出炉