中缀表达式转换为后缀表达式(python实现)
2019-06-14 08:04:49来源:博客园 阅读 ()
中缀表示式转换为后缀表达式 需要一个存放操作符的栈op_stack,输出结果的列表output 步骤: 从左到右遍历表达式: 1. 若是数字,直接加入到output 2. 若是操作符,比较该操作符和op_stack中操作符的优先级,若优先级大于op_stack中的,则压入到op_stack中 否则,将op_stack中优先级大于或等于该操作符优先级的所有操作符加入到output中,然后压入op_stack中 3. 若是左括号,压入到op_stack中 4. 若是右括号,将op_stack中所有左括号前面的操作符加入到output中 重复上面的步骤 后缀表达式求值 需要一个存放中间结果的栈num_stack 步骤: 从左到右遍历表达式: 1. 若是数字,压入到num_stack中 2. 若是操作符,取出num_stack中的前两个元素,第二个是表达式左边的操作数,计算表达式的值,将求值结果压入到num_stack中
python代码实现
from linked_stack import LinkedStack def infix2postfix(expression): output = [] op_stack = LinkedStack() op_priority = {'*': 2, '/': 2, '%': 2, '+': 1, '-': 1, '(': 0, ')': 0} for e in expression: if e == '(': op_stack.push(e) elif e == ')': while op_stack.first() != '(': output.append(op_stack.pop()) op_stack.pop() elif e.isdigit(): output.append(e) else: while not op_stack.is_empty() and op_priority[op_stack.first()] >= op_priority[e]: output.append(op_stack.pop()) op_stack.push(e) while not op_stack.is_empty(): output.append(op_stack.pop()) return ''.join(output) def postfix_eval(expression): num_stack = LinkedStack() for e in expression: if e.isdigit(): num_stack.push(e) else: num1 = num_stack.pop() num2 = num_stack.pop() res = eval(num2 + e + num1) num_stack.push(str(res)) return num_stack.pop() if __name__ == "__main__": print(infix2postfix('2+(3+5)*(6+4)*(8+3)')) print(postfix_eval('235+64+*83+*+'))
完整的栈代码实现以及中缀表达式转换为前缀表达式可以参考xxpassswd github
原文链接:https://www.cnblogs.com/time-read/p/11022977.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:断言
- python学习-53 正则表达式 2019-08-13
- 2.时间戳转换时间字符串函数 2019-07-24
- python列表生成式、键盘输入及类型转换、字符串翻转、字母大 2019-07-24
- windows+pychram+python3 将py程序转换成可执行文件EXE 2019-07-24
- python中的进制转换和原码,反码,补码 2019-07-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash